LeetCode 498. 对角线遍历

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

题目描述

✅ 498. 对角线遍历

image-20260928202008644

image-20260928202008645

题意分析

从矩阵左上角开始，沿右上、左下交替的方向，依次读取每一条斜对角线，返回包含全部元素的一维数组。每个格子恰好输出一次，矩阵不一定是正方形。

与其在每一步处理碰到上、下、左、右边界后的转向，不如先确定当前属于哪条对角线，再按该条线的方向输出。沿这两种斜向移动时，行号加列号始终不变，可以用这个和给对角线编号。

解法：按对角线编号枚举

核心思路

[!blue]

令 d = row + col。同一条对角线上的格子共享这个编号，左上角编号为 0，右下角为 m + n - 2，所以共有 m + n - 1 条线。按 d 递增处理，就按题目要求从左上逐条推进到右下。

固定 d 后，只要确定行号，列号就由 col = d - row 唯一确定。行本身要求 0 <= row <= m - 1；列必须满足 0 <= d - row <= n - 1，等价于 d - n + 1 <= row <= d。取两组范围的交集，得到 low = max(0, d - n + 1)、high = min(d, m - 1)。

偶数编号的对角线从左下向右上走，因此行号从 high 递减到 low，列号随之递增；奇数编号从右上向左下走，行号从 low 递增到 high。改变的是这条线内部的读取顺序，合法范围始终相同。

每个格子都有唯一的行列和，所以不会出现在两条不同对角线中；对每条线枚举全部合法行，又覆盖了线上所有格子。因此按上述编号和方向输出，不会遗漏、重复或越界。单行、单列时，每条线自然只包含一个合法位置，无需额外分支。

解题步骤

  1. 读取行数 m、列数 n，创建长度为 m * n 的结果数组，写指针 idx 从 0 开始。
  2. 枚举对角线编号 d = 0 到 m + n - 2。
  3. 计算本条线的合法行范围 [low, high]。
  4. 若 d 为偶数，行号从大到小枚举；否则从小到大枚举。
  5. 每个位置的列号都取 d - row，将对应元素写入 ans[idx] 后推进写指针。

代码实现

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++) {
            // 由列号等于 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++ {
        // 由列号等于 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)$，不计必须返回的结果数组，只使用常数个变量。

关键点总结

[!green]

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

易错点总结

[!yellow]

  • 编号多枚举一条：最后一条编号是 m + n - 2，循环上界不包含 m + n - 1。
  • 行下界漏掉 +1：列最大只能是 n - 1，对应行至少为 d - n + 1。
  • 奇偶方向写反：偶数编号向右上走，行号递减；奇数编号向左下走，行号递增。
  • 把列号当作一维下标换算：这里固定的是行列和，列号应为 d - row，不需要除以行数或列数。
  • 只使用行边界：合法行必须同时满足列范围，取两组范围交集后才适用于非方阵与单行、单列。

相似题目

题目 难度 关联与区别
1424. 对角线遍历 II 中等 同样按行列和确定对角线，原题各行长度不同，不能依赖规则矩形的固定边界。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/82262053
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！