LeetCode 1424. 对角线遍历 II

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 小米
标签
数组 排序 堆（优先队列）

题目描述

✅ 1424. 对角线遍历 II

image-20260928235407752

image-20260928235407753

题意分析

各行长度可以不同，要按图中的方向输出真实存在的元素：先处理靠左上的对角线，每条对角线再从左下向右上读取。

沿同一条对角线向右上移动时，行号减一、列号加一，所以 row+col 保持不变。这个和就是对角线编号；题目要求编号递增，同一编号内行号递减。由此可以先按编号分组，再调整每组内部的读取方向。

解法：按对角线分组

核心思路

[!blue]

groups[d] 存放编号为 d 的对角线上的元素，total 记录实际元素总数。逐行遍历，每行只扫描自己的长度，把 nums[row][col] 放入 groups[row+col]；若分组数组还没有这个下标，就先扩展到该编号。

扫描时行号递增，而一条对角线在同一行至多有一个元素，因此每个桶内的加入顺序就是行号递增。输出时反向读取这个桶，就得到行号递减，也就是从左下到右上的顺序；不同桶则按编号从小到大读取。

每个实际元素都有唯一的 row+col，所以只会进入一个桶，并在输出时恰好取出一次。桶编号和桶内方向又分别满足题目的两级顺序要求，因此结果既不重不漏，也按规定排列。整行遍历不依赖相邻格子是否存在，行长不齐不会破坏分组。

Java 先用 total 创建定长结果数组，再用 index 指向下一待写位置；Go 用 total 预留结果切片容量，再按顺序追加。两种写法都依据真实元素数分配结果。

解题步骤

  • 逐行按各自行长扫描。
  • 计算对角线编号，按需建立桶并追加。
  • 按编号遍历桶，每桶从后向前写入结果。

代码实现

class Solution {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        List<List<Integer>> groups = new ArrayList<>();
        int total = 0;

        for (int row = 0; row < nums.size(); row++) {
            List<Integer> line = nums.get(row);

            for (int col = 0; col < line.size(); col++) {
                // 相同行列和属于同一对角线，按行扫描会使桶内行号递增
                int diagonal = row + col;

                // 按需扩展到当前编号，不假设每条对角线长度相同
                while (groups.size() <= diagonal) {
                    groups.add(new ArrayList<>());
                }

                groups.get(diagonal).add(line.get(col));
                total++;
            }
        }

        int[] ans = new int[total];
        int index = 0;

        for (List<Integer> group : groups) {
            // 桶内逆序输出，得到行号递减的要求
            for (int i = group.size() - 1; i >= 0; i--) {
                ans[index++] = group.get(i);
            }
        }

        return ans;
    }
}

func findDiagonalOrder(nums [][]int) []int {
    groups := make([][]int, 0)
    total := 0

    for row := 0; row < len(nums); row++ {
        for col := 0; col < len(nums[row]); col++ {
            // 相同行列和属于同一对角线，按行扫描会使桶内行号递增
            diagonal := row + col
            // 按需扩展到当前编号，不假设每条对角线长度相同
            for len(groups) <= diagonal {
                groups = append(groups, nil)
            }
            groups[diagonal] = append(groups[diagonal], nums[row][col])
            total++
        }
    }

    ans := make([]int, 0, total)
    for _, group := range groups {
        // 桶内逆序输出，得到行号递减的要求
        for i := len(group) - 1; i >= 0; i-- {
            ans = append(ans, group[i])
        }
    }
    return ans
}

复杂度分析

设实际元素总数为 $N$。对于任何存在的格子 (row, col)，前面的 row 行各至少有一个元素，当前行至少有 col+1 个元素，所以 row+col+1 <= N，分组数组的长度不会超过 $N$。

  • 时间复杂度：$O(N)$。每个元素入桶与出桶各一次，所有扩容循环合计也只创建至多 $N$ 个桶。
  • 空间复杂度：$O(N)$。分组保存全部元素，桶数量和返回数组长度也都不超过 $N$。

关键点总结

[!green]

  • 分组由坐标决定，桶内反向来自扫描顺序。
  • 当前行长度决定内层界限。
  • 题目保证每行非空，才能用实际元素总数约束最大对角线编号。

易错点总结

[!yellow]

  • 按第一行长度扫描所有行，会越界或漏项。
  • 桶内正向输出，会反转题目要求的同线方向。
  • 用矩形面积估算结果长度，不适合锯齿输入。
  • 不需要交替改变对角线方向，本题每条对角线都从左下向右上读取；单行或单列时各元素也会按编号依次输出。

相似题目

题目 难度 关联与区别
498. 对角线遍历 中等 对角线编号仍可用行列和，原题是规则矩阵，本题各行长度不同，需要按已有元素分组遍历。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/82818286
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！