对角线.md

LeetCode 498对角线【中】详细图解

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示

思路1（本人，运行时间打败75%Java提交）###

第一步：####

观察到数字遍历轨迹分为两种，一种是斜向上，一种是斜向下。 的

对应方法：在复制到新数组中进行计数，偶数向上，奇数向下，用%2控制

int k = 0;
if(k % 2 == 0){
    斜向上代码
        if (触发换向)
            k++
}else{
    斜向下代码
        if (触发换向)
            k++
}

第二步：####

触发换向边界条件控制，包在中间的好办，碰到边界就平行侧移，向下遍历会在初始那几趟的末端没有到底就转到向上，同理向上遍历在后面碰不到顶边就会换方向。可以看到右侧的蓝色点，碰到右边就纵坐标下移一位。因此一共有四种转换点：

触发换向?
向上{
向上碰上壁右弹（横坐标+1， 纵坐标不变）；

向上碰右壁下弹 （横坐标不变，纵坐标 + 1）；
}

向下{
向下碰下壁右弹 （横坐标 + 1，纵坐标不变）；

向下碰左壁下弹（横坐标 不变，纵坐标 + 1）；  
}

第三步：####

还有个隐藏的问题，在我提交答案报错后才发现，发现向上遍历碰上壁右弹出现数组越界，这是因为判断向上碰上壁 先于 向上碰右壁，如果出现这种上壁和右壁都碰的情况下会产生错误。只需要把判断碰右壁的语句先于判断碰上壁即可（或者顺序不变在原来的判断上做下改动）。

完整代码####

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
        return new int[]{};
        }
        int i = 0;
        int j = 0;
        int r = matrix.length;
        int c = matrix[0].length;
        int[] res = new int[r * c];
        int k = 0;
        for(int count = 0; count < r * c; count++ ){
            // System.out.println(matrix[j][i]);
            res[count] = matrix[j][i];
            if(k % 2 == 0){
                //向上遍历
                if(j == 0 && i != c - 1){
                    //碰上壁,右移
                    i += 1;
                    k++;
                }else if( i == c - 1){
                    //碰右壁，下移
                    j += 1;
                    k++;
                }else{
                    //正常上移
                    j--;
                    i++;                 
                }                             
            }else{
                //向下遍历
                if(i == 0 && j != r - 1){
                   //碰左壁
                    j++;
                    k++;
                }else if( j == r - 1){
                    //碰下壁
                    i++;
                    k++;
                }else{
                    //正常下移
                    i--;
                    j++;
                    
                }
            }
        }
        return res;
        }
    }