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
            






Last updated

Was this helpful?