杨氏矩阵又叫杨氏图表，它是这样一个矩阵，满足条件：
(1)如果格子(i,j)没有元素，则它右边和上边的相邻格子也一定没有元素。
(2)如果格子(i,j)有元素a[i][j]，则它右边和上边的相邻格子要么没有元素，要么有元素且比a[i][j]大。
1 ~ n所组成杨氏矩阵的个数可以通过下面的递推式得到：
如图就是n=3时的杨氏矩阵。
下面介绍一个公式，那就是著名的钩子公式。
对于给定形状，不同的杨氏矩阵的个数为：n！除以每个格子的钩子长度加1的积。其中钩子长度定义为该格子右边的格子数和
它上边的格子数之和。
题目：http://poj.org/problem?id=1825
介绍完了钩子公式，那么我们可以来做一道基础题了。
题目：给四行，第一行放5个数字，第二行放三个数字，第三行放3个数字，第四行放1个数字，都是左对齐的排列，现有1~12
共12个数字，要求放到这四行中，从上到下，从左到右都是按小到大排列，问你共有几种排法？（如图所示）
() () () () ()
() () ()
() () ()
()
这个问题直接利用钩子公式解决即可。
杨氏矩阵既可以用来当堆，又可以当成平衡树。通常杨氏矩阵会涉及到两个问题：
(1)在杨氏矩阵中查找值为x的元素 (2)在杨氏矩阵中找第K大的元素
对于第一个问题，其实有两种方法，第一种方法就是二分查找法，这种方法的时间效率不是很好。第二种方法就是类堆查找
法。方法是这样的：从矩阵的右上角出发，对于元素a[i][j]，如果a[i][j]==x，则找到元素x，直接返回； 如果a[i][j]
> x，则向下移动，即继续比较a[i+1][j]与x；如果a[i][j] < x，则向左移动，即继续比较a[i][j-1]与x。该算法的时间
复杂度是O(m+n)。
bool Find(int a[][N],int n,int m,int x)
{
assert(a != NULL && n > 0 && m > 0);
int row = 0;
int col = m - 1;
while(row <= n - 1 && col >= 0)
{
if(a[row][col] == x) return true;
else if(a[row][col] > x) col--;
else row++;
}
return false;
}
对于第二个问题，首先，二分枚举找到一个数x，它比杨氏矩阵中k个数大；然后，利用类堆查找法找到刚好小于x的元素。该算
法的时间复杂度为O((m+n)log(mn))，但不需要额外存储空间。
int get_order(int a[][N],int n,int m,int k)
{
int row = 0;
int col = m - 1;
int order = 0;
while(row <= n - 1 && col >= 0)
{
if(a[row][col] < k)
{
order += col + 1;
row++;
}
else col--;
}
return order;
}
int Find_Kth_Num(int a[][N],int n,int m,int k)
{
int low = a[0][0];
int high = a[n-1][m-1];
int order = 0;
int mid = 0;
do
{
mid = (low + high) >> 1;
order = get_order(a,n,m,mid);
if(order == k) break;
else if(order > k) high = mid - 1;
else low = mid + 1;
}while(1);
int row = 0;
int col = m - 1;
int ret = mid;
while(row <= n - 1 && col >= 0)
{
if(a[row][col] < mid)
{
ret = max(ret,a[row][col]);
row++;
}
else col--;
}
return ret;
}