题目主要信息

给定一个大小为 n*m 的矩阵，请以对角线遍历并返回遍历结果

方法一：翻转输出

具体方法

• 新建一个数组result，存储最终的结果
• 使用一个循环遍历所有的对角线，第一行和最后一列的元素都是对角线的起点
• 使用一个内层循环对所有对角线上的所有元素，可以计算指定对角线上的元素数量
• 由于不知道每条对角线的元素数量，需要为每条对角线分配一个列表或者动态数组，但是同样也可以计算机当前对角线的元素数量。
• 对于奇数编号的对角线，只需要将迭代结果翻转在加入结果数组即可。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型二维数组 
     * @return int整型一维数组
     */
    public int[] diagonalOrder (int[][] mat) {
        // write code here
                // Check for empty matrices
        if (mat.length == 0) {
            return new int[0];
        }
        
        int N = mat.length;
        int M = mat[0].length;
        
      // 结果集合
        int[] result = new int[N*M];
        int k = 0;
        ArrayList<Integer> intermediate = new ArrayList<Integer>();
        // 遍历数组
        for (int d = 0; d < N + M - 1; d++) {
            intermediate.clear();
            int r = d < M ? 0 : d - M + 1;
            int c = d < M ? d : M - 1;
            
            while (r < N && c > -1) {
                
                intermediate.add(mat[r][c]);
                ++r;
                --c;
            }
              
          // 偶数行 
            if (d % 2 == 0) {
                Collections.reverse(intermediate);
            }
            
            for (int i = 0; i < intermediate.size(); i++) {
                result[k++] = intermediate.get(i);
            }
        }
        return result;

    }
}

复杂度分析

• 时间复杂度：$O(N\cdot M)O(N\cdot M)$，数组有$N\mathrm{行}MN\; 行\; M$列。对于所有奇数对角线上的元素，需要两次处理，迭代和翻转。为了节省空间，需要遍历新对角线之前清除中间使用的空间，该操作需要 $O(K)O(K)$的复杂度度，其中 K 是数组长度。因此至少处理两次数组中的元素，渐进复杂度为 $O(N\cdot M)O(N\cdot M)$。
• 空间复杂度：$O(min(N,M))O(min(N,M))$，额外空间用于存储每条对角线的中间数组，该数组长度为$NN$和 $MM$的最小值。注意：对角线延伸到索引超出范围结束。

方法二：模拟

具体方法

按照题目要求，模拟在数组中的行走路线，得到想要的遍历顺序。为了实现此模拟，必须清楚数组内部的行走策略。对每条对角线需要明确两件事情：

知道该对角线的行走方向。

确定对角线的起点元素，这取决于对角线的行走方向。

流程：

1、初始化一个布尔变量 $directiondirection$表示当前对角线的方向。根据当前方向和尾部位置确定下一条对角线首部。最初 $directiondirection$ 为 1，方向向上。每条对角线遍历完成后更新 $directiondirection$。

2、假设当前对角线首部为 $mat[i][j]mat[i]\; [j]$，根据方向遍历该对角线。

• 向上的对角线，下一个元素是$mat[i\mathrm{-}1][j+1]mat[i-1]\; [j+1]$。
• 向下的对角线，下一个元素是$mat[i+1][j\mathrm{-}1]mat[i+1]\; [j-1]$。

3、遍历当前对角线元素直到到达矩阵边界结束。

4、假设现在到达当前对角线的最后一个元素，寻找下一条对角线首部。注意：下面伪代码中方向是当前对角线方向。如果当前对角线方向是向上的，则下一条对角线是向下的；否则是下一条对角线是向上的。

5、继续处理对角线元素，当前对角线遍历结束时，使用当前方向和尾部位置找出下一条对角线首部。然后翻转方向，处理下一条对角线。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型二维数组 
     * @return int整型一维数组
     */
    public int[] diagonalOrder (int[][] mat) {
        if (mat == null || mat.length == 0) {
            return new int[0];
        }
        
 
        int N = mat.length;
        int M = mat[0].length;
        
        int row = 0, column = 0;
        

        int direction = 1;

        int[] result = new int[N*M];
        int r = 0;
        
        //迭代数组中的所有元素
        while (row < N && column < M) {
            
// 首先，将当前元素添加到结果矩阵中。
            result[r++] = mat[row][column];
            // 根据当前方向沿当前对角线移动。[i，j]->[i-1，j+1]如果上升，而[i，j]->[i+1][j-1]如果下降。
            int new_row = row + (direction == 1 ? -1 : 1);
            int new_column = column + (direction == 1 ? 1 : -1);
            
//检查对角线中的下一个元素是否在矩阵的边界内。如果不在范围内，我们必须找到下一个开头
            if (new_row < 0 || new_row == N || new_column < 0 || new_column == M) {
                
                if (direction == 1) {
                    // 对于尾为[i，j]的向上对角线，如果[i，j+1]在边界内，则它成为下一个头部。否则，正下方的元素即元素[i+1，j]将成为下一个he
                    row += (column == M - 1 ? 1 : 0) ;
                    column += (column < M - 1 ? 1 : 0);
                        
                } else {
                    
//对于以[i，j]为尾部的向下的对角线，如果[i+1，j]在边界内，则它成为下一个头部。否则，正下方的元素即元素[i，j+1]成为下一个头
                    column += (row == N - 1 ? 1 : 0);
                    row += (row < N - 1 ? 1 : 0);
                }
                direction = 1 - direction;        
                        
            } else {
                
                row = new_row;
                column = new_column;
            }
        }
        return result;      

    }
}

复杂度分析

• 时间复杂度：$O(N\cdot M)O(N\cdot M)$，每个元素只处理一次。
• 空间复杂度：$O(1)O(1)$，不使用额外空间。注意：输出数组空间不计入空间复杂度，因为这是题目要求的空间。空间复杂度应该指除了最终数组以外的空间。上一个方法中是中间数组，该方法中只有几个变量。