LeetCode 498. 对角线遍历

约 5 分钟
文章信息 16 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 未掌握 20-50 字节跳动 美团 阿里巴巴 快手 腾讯 猿辅导 百度 华为 拼多多 旷视
标签
数组 矩阵 模拟 矩阵问题
目录

题目描述

✅ 498. 对角线遍历

image-20230305143540755

题意分析

给定一个 $m \times n$ 的矩阵，要求把全部元素按「对角线蛇形」的次序装进一个一维数组返回：先沿一条斜线从左下往右上走完，再沿下一条斜线从右上往左下走回来，如此反复，直到所有格子都被访问过一次。

题目给出的约束里有两个明确信号。其一，输出长度恰好是 $m \cdot n$，说明每个元素不多不少访问一次，不存在跳过或重复，这就把「循环要跑多少次」这个问题提前定死了。其二，$m$ 和 $n$ 都可以低到 1，也就是说单行矩阵和单列矩阵都是合法输入，而这两种形状恰好会让「拐弯」发生在每一步，是最容易写挂的输入。

需要留意的边界还有一个：题目只要求返回顺序，没有额外的空间限制，因此结果数组本身不算进额外开销，真正要控制的是除结果之外还用了多少变量。

另外注意输出次序是从矩阵左上角 mat[0][0] 出发的，第一条斜线只有它一个元素，所以起手方向必须是「往右上」，否则整个序列就反了。

解法：按方向模拟对角线行走

核心思路

问题关键：同一条对角线上的坐标都满足 row + col = d，对角线编号 d 从 0 到 m + n - 2。题目要求的蛇形顺序，本质上只是相邻对角线采用相反的遍历方向。

为什么按对角线编号枚举：逐格移动需要处理上、下、左、右四种碰壁情况；直接固定 d 后，只需确定这一条线合法的行范围：

\[low=\max(0,d-n+1), \quad high=\min(d,m-1)\]

列号始终由 col = d - row 得到。d 为偶数时，从 high 到 low 枚举行，方向是右上；d 为奇数时，从 low 到 high 枚举行，方向是左下。

不变量与正确性：开始处理第 d 条对角线时，所有坐标和小于 d 的格子已经按要求写入。区间 [low, high] 恰好包含所有满足 row + col = d 的合法行，每行又唯一对应一列，因此本轮不重不漏；奇偶性决定的方向与题目要求一致。处理完最后一个 d 后，矩阵的每个格子恰好输出一次。

解题步骤

  • 创建长度为 m * n 的结果数组，并维护写入位置 idx。
  • 枚举对角线编号 d = 0 ... m+n-2。
  • 计算本条对角线的合法行区间 [low, high]。
  • d 为偶数时行号递减，为奇数时行号递增；列号统一取 d - row。
  • 全部对角线处理完后返回结果。

对 [[1,2,3],[4,5,6],[7,8,9]]，各条对角线依次输出 [1]、[2,4]、[7,5,3]、[6,8]、[9]，合并后得到 [1,2,4,7,5,3,6,8,9]。

代码实现

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] ans = new int[m * n];
        int idx = 0;

        for (int d = 0; d < m + n - 1; d++) {
            int low = Math.max(0, d - n + 1);
            int high = Math.min(d, m - 1);
            if ((d & 1) == 0) {
                for (int row = high; row >= low; row--) {
                    ans[idx++] = mat[row][d - row];
                }
            } else {
                for (int row = low; row <= high; row++) {
                    ans[idx++] = mat[row][d - row];
                }
            }
        }
        return ans;
    }
}

func findDiagonalOrder(mat [][]int) []int {
    m, n := len(mat), len(mat[0])
    ans := make([]int, m*n)
    idx := 0

    for d := 0; d < m+n-1; d++ {
        low := max(0, d-n+1)
        high := min(d, m-1)
        if d%2 == 0 {
            for row := high; row >= low; row-- {
                ans[idx] = mat[row][d-row]
                idx++
            }
        } else {
            for row := low; row <= high; row++ {
                ans[idx] = mat[row][d-row]
                idx++
            }
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(mn)$，每个格子恰好写入一次。
  • 空间复杂度：$O(1)$，不计必须返回的结果数组，只使用常数个变量。

关键点总结

  • row + col 相同的格子属于同一条对角线。
  • 合法行范围由行边界和列边界共同推出，列号直接用 d - row 计算。
  • 偶数对角线行号递减，奇数对角线行号递增。
  • 按对角线枚举避免维护移动方向和多组拐弯分支，单行、单列也自然成立。

易错点总结

  • 对角线数量写成 m + n：会多处理一条空对角线；正确数量是 m + n - 1。
  • 行范围少了 +1：low 应为 d - n + 1，否则 col = d-row 可能等于 n 而越界。
  • 奇偶方向写反：起点 (0,0) 所在的第 0 条对角线按右上方向，因此偶数对角线必须让行号递减。
  • 列号除以行数或列数：本解法不是一维展开，列号始终是 d - row。
  • 只按方阵验证：1 \times n、m \times 1 和非方阵更容易暴露边界公式错误。

相似题目

题目 难度 考察点
1424. 对角线遍历 II 中等 锯齿数组下改用 i + j 分桶，方向模拟失效
54. 螺旋矩阵 中等 四边界收缩式模拟，拐弯靠边界内移而非奇偶翻转
59. 螺旋矩阵 II 中等 同样的螺旋次序反过来用于填值而非读值
48. 旋转图像 中等 原地坐标映射，考察四元素轮换而非顺序遍历
867. 转置矩阵 简单 最简单的下标互换，作为坐标变换类的入门对照
566. 重塑矩阵 简单 一维下标与二维坐标的相互换算
73. 矩阵置零 中等 用首行首列当标记位，考察 $O(1)$ 额外空间的技巧