What is the main pattern behind Diagonal Traverse?

The main pattern is summing row and column indices to identify diagonals and alternating the traversal direction for each diagonal.

Can Diagonal Traverse handle non-square matrices?

Yes, the solution correctly handles any m x n matrix within the given constraints using the same diagonal summing logic.

Why do some diagonals need to be reversed?

Reversing every other diagonal ensures the zig-zag order is maintained, matching the problem's required output sequence.

What is the time complexity of Diagonal Traverse?

Each element is visited once, so the time complexity is O(M*N), where M and N are matrix dimensions.

How does the array plus matrix pattern apply here?

Each diagonal is treated as an array derived from matrix indices; collecting elements efficiently into a single output array follows the pattern precisely.

#498

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

对角线遍历

给你一个大小为 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]] 输…

数组矩阵模拟

题目描述

给你一个大小为 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⁴
1 <= m * n <= 10⁴
-10⁵ <= mat[i][j] <= 10⁵

lightbulb

解题思路

方法一：定点遍历

对于每一轮 $k$ ，我们固定从右上方开始往左下方遍历，得到 $t$ 。如果 $k$ 为偶数，再将 $t$ 逆序。然后将 $t$ 添加到结果数组 $\textit{ans}$ 中。

问题的关键在于确定轮数以及每一轮的起始坐标点 $(i, j)$ 。

时间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        ans = []
        for k in range(m + n - 1):
            t = []
            i = 0 if k < n else k - n + 1
            j = k if k < n else n - 1
            while i < m and j >= 0:
                t.append(mat[i][j])
                i += 1
                j -= 1
            if k % 2 == 0:
                t = t[::-1]
            ans.extend(t)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(M*N) as each element is visited exactly once. Space complexity is O(1) extra if output array is not counted; using only loop variables and flags.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate starts by recognizing the diagonal index sum pattern.
question_mark
Candidate correctly alternates traversal direction per diagonal.
question_mark
Candidate efficiently handles matrix boundaries without errors.

warning

常见陷阱

外企场景

error
Incorrectly reversing elements on diagonals leading to wrong order.
error
Off-by-one errors when accessing the last row or column.
error
Using extra space unnecessarily instead of in-place collection into the result array.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Traverse diagonals starting from bottom-right instead of top-left.
arrow_right_alt
Return only the elements of even-numbered diagonals.
arrow_right_alt
Perform the traversal but output each diagonal as a separate subarray instead of flattening.

help

常见问题

外企场景

继续练习

#566 重塑矩阵 #289 生命游戏 #749 隔离病毒