498. Diagonal Traverse

对角线 matrix坐标

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

Constraints:

• m == mat.length

• n == mat[i].length

• 1 <= m, n <= 104

• 1 <= m * n <= 104

• -105 <= mat[i][j] <= 105

分析:

对角线方向	公式	k取值范围	应用题目	是否对称轴
↘ 主对角线	i - j == k	k ∈ [-(n-1), m-1]	1329, N-Queens, matrix diagonal sort	✅ 是主对称轴（i==j）
↙ 反对角线	i + j == k	k ∈ [0, m+n-2]	498, 1424, N-Queens, TicTacToe	❌ 不是对称轴
主对角线中心线	i == j	k=0 (i-j=0)	Transpose, isSymmetric	✅ 经典

利用对角线原理 正向对角线 x-y = k 反向对角线 x+y = k

同理可以对对角线组操作，对角线总数 m+n-1

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        if not mat or not mat[0]:
            return []
        res = []
        n,m = len(mat), len(mat[0])
        for k in range(n+m-1):
            path = []
            for i in range(n):
                j = k - i
                if 0 <= j < m:
                    path.append(mat[i][j])
            if k%2 == 0:
                path.reverse()
            res += path
        return res

1. 初始检查：首先检查输入矩阵是否为空。

2. 初始化参数：设置矩阵的行数 n 和列数 m，初始化结果列表 res，起始位置 (row, col) 和初始方向 direction（1 表示右上，-1 表示左下）。

3. 遍历矩阵：使用 for 循环遍历矩阵的所有元素。

4. 添加当前元素：将当前位置的元素 mat[row][col] 加入结果列表 res。

5. 计算下一个位置：根据当前方向计算下一个位置 (new_row, new_col)。

6. 边界检查：

   • 如果下一个位置在矩阵范围内，更新当前位置。

   • 如果超出范围，根据当前方向调整位置并改变方向。

7. 返回结果：最终返回按对角线顺序遍历的结果列表 res。

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        if not mat or not mat[0]:
            return []
        res = []
        n,m=len(mat),len(mat[0])
        row,col = 0,0
        dir = 1 #1 up, -1 down
        for _ in range(n*m):
            res.append(mat[row][col])
            new_col = col + (1 if dir == 1 else -1)
            new_row = row + (-1 if dir == 1 else 1)
            if 0<=new_row<n and 0<=new_col<m:
                row,col=new_row,new_col
            else:
                if dir==1:
                    if 0<=col + 1<m:
                        col += 1
                    else:
                        row += 1
                else:
                    if 0<=row+1<n:
                        row += 1
                    else:
                        col += 1
                dir *= -1
        return res