T498、对角线遍历

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
示例:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]

输出: [1,2,4,7,5,3,6,8,9]
解释:
说明:
给定矩阵中的元素总数不会超过 100000。

解

使用一个方向up表示当前是向上还是向下遍历，需要考虑边界方向转换时的特殊情况。优先判断矩阵右下角时的转向下标变化。

 public int[] findDiagonalOrder(int[][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0].length==0)
            return new int[0];
        int up = 1;
        int x = matrix.length, y = matrix[0].length;
        int len = x * y, idx = 0;
        int i = 0,j = 0;
        int []res = new int[len]; 
        while(idx<len){
            res[idx] = matrix[i][j];
            idx++;
            if(up==1){//向上
                if(i==0||(j+1)==y)
                    up = -up;
                if((j+1)==y) // 到右边界
                    i++;
                else if(i==0) // 到上边界
                    j++;
                else{
                    i--;j++;
                }
            }else if(up==-1){ // 向下
                if(j==0||(i+1)==x)
                    up = -up;
                if((i+1)==x) // 到下边界
                    j++;
                else if(j==0) // 到左边界
                    i++;
                else{
                    i++;j--;
                }
            }
        }
        return res;
    }