题目

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,4,7,5,3,6,8,9]

示例 2：

输入：mat = [[1,2],[3,4]] 输出：[1,2,3,4]

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 10^4
1 <= m * n <= 10^4
-10^5 <= mat[i][j] <= 10^5

解题思路

把问题看作：

找到第一条对角线。
确定它的方向，从头走到尾。
找到第二条对角线。
确定它的方向，从头走到尾。
...以此类推，直到走完所有对角线。

1.识别所有对角线

首先，我们需要一个方法来唯一标识每一条对角线。通过观察可以发现一个关键规律： 同一条对角线上的所有元素，其坐标 (row, col) 的和 row + col 是一个固定的值。

mat[0][0] -> 0 + 0 = 0 (第 0 条对角线)
mat[0][1], mat[1][0] -> 0 + 1 = 1, 1 + 0 = 1 (第 1 条对角线)
...
mat[n-1][m-1] -> (n-1) + (m-1) (最后一条对角线)

所以，我们可以用 i = row + col 作为对角线的索引。这个索引 i 从 0 开始，一直到 (n-1) + (m-1) 结束。这就是代码中外层 for 循环 for (int i = 0; i < n + m - 1; i++) 的由来。

2.确定每条对角线的遍历方向

遍历方向是交替的，“右上”和“左下”轮换。这和对角线索引 i 的奇偶性完美对应：

当 i 为偶数 (0, 2, 4, ...)，方向是向右上（row 减小，col 增大）。
当 i 为奇数 (1, 3, 5, ...)，方向是向左下（row 增大，col 减小）。

这就是代码中 if (i % 2 == 0) 用来区分两种情况的原因。

3.找到每条对角线的“起点”

一旦确定了对角线 i 和它的方向，我们只需要找到这条线的起点，然后就可以一直走到底了。

对于向右上（row--, col++）的偶数对角线：

它的遍历是从“左下”到“右上”的。所以，它的起点是这条线上最靠左下角的那个元素。
这个起点要么在矩阵的第一列 (col = 0)，要么在矩阵的最后一行 (row = n - 1)。
判断依据：
- 当对角线索引 i 比较小 (i < n) 时，起点肯定在第一列。此时 col = 0，因为 row + col = i，所以 row = i。
- 当 i 增大到一定程度 (i >= n)，起点就跑到最后一行了。此时 row = n - 1，所以 col = i - row = i - (n - 1)。
这就是代码 int row = (i < n) ? i : n - 1; 和 int col = (i < n) ? 0 : i - (n - 1); 的逻辑。

对于向左下（row++, col--）的奇数对角线：

它的遍历是从“右上”到“左下”的。所以，它的起点是这条线上最靠右上角的那个元素。
这个起点要么在矩阵的第一行 (row = 0)，要么在矩阵的最后一列 (col = m - 1)。
判断依据：
- 当对角线索引 i 比较小 (i < m) 时，起点肯定在第一行。此时 row = 0，所以 col = i。
- 当 i 增大到一定程度 (i >= m)，起点就跑到最后一列了。此时 col = m - 1，所以 row = i - col = i - (m - 1)。
这就是代码 int row = (i < m) ? 0 : i - (m - 1); 和 int col = (i < m) ? i : m - 1; 的逻辑。

4.沿确定方向遍历单条对角线

一旦找到了起点 (row, col) 和方向（比如 row--, col++），剩下的就很简单了：

使用一个 while 循环。
循环的条件就是检查当前坐标 (row, col) 是否还在矩阵的边界之内。
在循环里，把当前元素加入结果数组，然后更新 row 和 col，向下一个点移动。

具体代码

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {

        int n = mat.size();      // 总行数
        int m = mat[0].size();   // 总列数
        vector<int> ans;
        
        // 总共有 n + m - 1 条对角线
        for (int i = 0; i < n + m - 1; i++) {
            if (i % 2 == 0) { // 偶数对角线，向右上遍历 (row--, col++)
                // 计算起点：
                // 如果对角线还在矩阵上半部分，起点在第一列；否则在最后一行
                int row = (i < n) ? i : n - 1;
                int col = (i < n) ? 0 : i - (n - 1);
                
                while (row >= 0 && col < m) {
                    ans.push_back(mat[row][col]);
                    row--;
                    col++;
                }
            } else { // 奇数对角线，向左下遍历 (row++, col--)
                // 计算起点：
                // 如果对角线还在矩阵上半部分，起点在第一行；否则在最后一列
                int row = (i < m) ? 0 : i - (m - 1);
                int col = (i < m) ? i : m - 1;

                while (row < n && col >= 0) {
                    ans.push_back(mat[row][col]);
                    row++;
                    col--;
                }
            }
        }
        return ans;
    }
};

498. 对角线遍历

beautifulremi

题目