LeetCode 1424. 对角线遍历 II

2023-11-28 HGNULB 约 6 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1424. 对角线遍历 II

题意分析

输入是一个二维数组，但每一行的长度可以互不相同，也就是所谓的锯齿数组。要求把所有元素按对角线顺序放进一个一维数组返回。

题目定义的顺序是：先按对角线从左上往右下一条条推进，每条对角线内部则从左下往右上读。用坐标描述就是——先按 row + col 从小到大分组，同一组内按 row 从大到小输出。

行长不齐是这题真正的难点信号。规则矩阵可以直接用两层循环沿对角线走，但锯齿数组里某一条对角线上的格子可能是断开的：(2,0) 存在、(1,1) 不存在、(0,2) 又存在，靠指针沿斜线移动会不断撞到不存在的下标。

约束里元素总数可达 $10^5$，所以需要线性或接近线性的做法；行数与最长行长各自都可能很大，但两者之积可能远大于元素总数，任何按「行数 × 最大列数」枚举的写法都会退化。

边界上要覆盖：某些行可能很短甚至只有一个元素；row + col 的最大值不等于「行数加最大列长」，必须实际统计。

解法：按对角线分组

核心思路

规则矩阵可以沿着斜线移动，但锯齿数组的中间坐标可能不存在。与其枚举坐标再反复判断越界，不如只遍历真实元素，并利用坐标规律分组。

坐标 (row, col) 所在的对角线编号是 row + col。按行优先顺序遍历时，把元素追加到对应编号的桶中。对于同一个桶，后加入的元素具有更大的 row；题目却要求每条对角线从左下到右上，也就是按 row 从大到小输出，因此最后把每个桶逆序读出即可，无需排序。

正确性来自以下两个不变量：

每个元素只进入编号为 row + col 的桶，所以同一桶恰好包含同一条对角线上的全部元素，不会遗漏或串组。

同一桶的入桶顺序是 row 递增，逆序读取后就是题目要求的 row 递减。

最后按对角线编号从小到大拼接各桶，既保证对角线之间的顺序，也保证对角线内部的顺序。

解题步骤

准备动态桶数组 groups 和元素计数 total。

按 row 从小到大遍历各行；每行只遍历自己的实际长度，避免对锯齿输入访问越界。

对每个元素计算 diagonal = row + col，按需创建桶，再将元素追加进去。

按 diagonal 从小到大访问所有桶，每个桶从末尾向开头写入答案。

以 [[1,2,3],[4],[5,6,7]] 为例，按行扫描得到：

桶 0：[1]

桶 1：[2,4]

桶 2：[3,5]

桶 3：[6]

桶 4：[7]

逆序读取每个桶，结果为 [1,4,2,5,3,6,7]。对角线 2 上的 (1,1) 不存在，但算法从未枚举这个坐标，因此既不会越界，也不会补入虚假元素。

代码实现

import java.util.ArrayList;
import java.util.List;

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$。

时间复杂度：$O(n)$。每个真实元素入桶一次、出桶一次，没有扫描不存在的矩阵位置。

空间复杂度：$O(n)$。桶中共保存 $n$ 个元素；题目保证每行非空，因此最大对角线编号也小于 $n$。返回数组另占 $O(n)$。

关键点总结

对角线的唯一分组键是 row + col；先按键分组，比在锯齿数组上模拟斜线更稳。

行优先遍历使同一桶内的 row 递增，题目要求 row 递减，因此逆序读取即可，不需要 $O(n \log n)$ 排序。

内层循环必须使用当前行的长度，不能假设所有行等长。

题目保证每行非空，所以桶数量也是 $O(n)$；代码仍能安全跳过空行，但若放宽为大量空行，空间上界应按最大 row + col 重新计算。

易错点总结

用第一行长度控制所有内层循环：短行会越界，长于第一行的部分又会被漏掉。

桶按入桶顺序正向输出：[[1,2],[3,4]] 的桶 1 会得到 2,3，正确顺序应是 3,2。

按元素值给桶排序：题目顺序由坐标决定，与数值大小无关。

分组键写成 row - col：会得到另一方向的对角线；本题必须使用 row + col。

用 行数 × 第一行长度 估算结果长度：锯齿输入下会多分配或少分配，应统计真实元素总数。

相似题目

题目	难度	考察点
498. 对角线遍历	中等	规则矩阵且方向逐条交替，重点在边界跳转规则
54. 螺旋矩阵	中等	按四条边收缩输出，考察边界变量的更新顺序
59. 螺旋矩阵 II	中等	反过来按螺旋顺序填值，验证同一套边界逻辑
867. 转置矩阵	简单	坐标互换的最简形式，非方阵时需另开结果数组
48. 旋转图像	中等	要求原地完成，靠转置加翻转组合出旋转
562. 矩阵中最长的连续1线段	中等	需要同时沿横、竖、两条对角线方向做递推