0498. Diagonal Traverse ======================= 题目信息 -------- :题号: 0498 :难度: Medium :主题: 矩阵、斜对角线、交替方向、完整遍历 :原题: `LeetCode 0498 `_ :重点: 从左上角开始、同一斜线上的坐标满足 ``row+col`` 相同、方向在右上和左下之间交替、每格恰好一次 题目重述 -------- 给定 ``m × n`` 整数矩阵 ``mat``,从左上角元素开始,按斜对角线顺序遍历所有元素。第一条可移动的斜线方向为右上;到达边界后转到下一条斜线并改为左下,之后每条斜线交替方向。 返回按访问顺序组成的一维数组。矩阵行列数均位于 ``[1, 10^4]``,总元素数不超过 ``10^4``,元素位于 ``[-10^5, 10^5]``。每个格子必须恰好访问一次。 自建示例 -------- 非方形矩阵: .. code-block:: text 输入:mat = [[1,2,3],[4,5,6]] 输出:[1,2,4,5,3,6] 解释:各条斜线依次为 [1]、[2,4]、[5,3]、[6],方向交替。 单列矩阵: .. code-block:: text 输入:mat = [[7],[8],[9]] 输出:[7,8,9] 解释:每条斜线只有一个元素,遍历顺序就是从上到下。 按 row + col 分组并交替反转 --------------------------- 同一条右上到左下斜线上的格子满足 ``row + col`` 相等,因此从 0 到 ``m+n-2`` 枚举这个和就能覆盖所有斜线。先按行递增、列递减收集一条斜线;当该斜线编号为偶数时反转,得到从左上开始向右上交替的题目顺序。 斜线起点由其编号决定:编号小于列数时从第一行开始,否则从最后一列、超出部分的行开始。之后同时向下、向左移动直到越界。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector findDiagonalOrder( std::vector>& mat) { int rows = static_cast(mat.size()); int columns = static_cast(mat[0].size()); std::vector result; result.reserve(rows * columns); for (int diagonal = 0; diagonal < rows + columns - 1; ++diagonal) { int row = diagonal < columns ? 0 : diagonal - columns + 1; int column = diagonal < columns ? diagonal : columns - 1; std::vector current; while (row < rows && column >= 0) { current.push_back(mat[row][column]); ++row; --column; } if (diagonal % 2 == 0) { std::reverse(current.begin(), current.end()); } result.insert(result.end(), current.begin(), current.end()); } return result; } }; 代码分析 -------- 每个格子只属于一个 ``row + col`` 分组,收集后按奇偶反转正好实现方向交替;起点公式覆盖了矩阵变宽或变高后的两段斜线。总时间复杂度为 ``O(rows * columns)``,临时斜线和结果数组之外的辅助空间最大为 ``O(min(rows, columns))``。