0498. Diagonal Traverse¶
题目信息¶
- 题号:
0498
- 难度:
Medium
- 主题:
矩阵、斜对角线、交替方向、完整遍历
- 原题:
- 重点:
从左上角开始、同一斜线上的坐标满足
row+col相同、方向在右上和左下之间交替、每格恰好一次
题目重述¶
给定 m × n 整数矩阵 mat,从左上角元素开始,按斜对角线顺序遍历所有元素。第一条可移动的斜线方向为右上;到达边界后转到下一条斜线并改为左下,之后每条斜线交替方向。
返回按访问顺序组成的一维数组。矩阵行列数均位于 [1, 10^4],总元素数不超过 10^4,元素位于 [-10^5, 10^5]。每个格子必须恰好访问一次。
自建示例¶
非方形矩阵:
输入:mat = [[1,2,3],[4,5,6]]
输出:[1,2,4,5,3,6]
解释:各条斜线依次为 [1]、[2,4]、[5,3]、[6],方向交替。
单列矩阵:
输入:mat = [[7],[8],[9]]
输出:[7,8,9]
解释:每条斜线只有一个元素,遍历顺序就是从上到下。
按 row + col 分组并交替反转¶
同一条右上到左下斜线上的格子满足 row + col 相等,因此从 0 到 m+n-2 枚举这个和就能覆盖所有斜线。先按行递增、列递减收集一条斜线;当该斜线编号为偶数时反转,得到从左上开始向右上交替的题目顺序。
斜线起点由其编号决定:编号小于列数时从第一行开始,否则从最后一列、超出部分的行开始。之后同时向下、向左移动直到越界。
C++ 实现¶
class Solution {
public:
std::vector<int> findDiagonalOrder(
std::vector<std::vector<int>>& mat) {
int rows = static_cast<int>(mat.size());
int columns = static_cast<int>(mat[0].size());
std::vector<int> 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<int> 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))。