LeetCode-Go 题解 | 498. Diagonal Traverse 对角线遍历：坐标轴模拟法与边界处理详解

LeetCode-Go 题解 | 498. Diagonal Traverse 对角线遍历：坐标轴模拟法与边界处理详解

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 第 498 题「Diagonal Traverse（对角线遍历）」，以 LeetCode-Go 仓库中 0498.Diagonal-Traverse 的题解文档为主体，深入讲解如何用模拟法按"之字形"对角线顺序遍历一个 M x N 矩阵。读完本文，你将掌握两种 Go 实现思路（方向数组法与边界状态机法）、完整的边界条件处理策略，以及仓库中配套测试用例所覆盖的各类退化场景，可直接复用于面试手写与同类矩阵遍历题目。

一、题目理解：什么是"对角线遍历"

原题描述

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素。

示例：

输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,4,7,5,3,6,8,9]

说明：给定矩阵中的元素总数不会超过 10,000。

遍历顺序解读

从示例输出[1, 2, 4, 7, 5, 3, 6, 8, 9]可以看出，遍历路径为：

1. 从左上角(0, 0)出发，先向右上方向（东北）移动：1 → 2；
2. 触碰上边界后转向左下方向（西南）：2 → 4 → 7；
3. 触碰左边界后再转向右上：7 → 5 → 3；
4. 触碰右边界后再转向左下：3 → 6 → 8 → 9，直到右下角结束。

即对角线方向在"右上（东北）"与"左下（西南）"之间交替切换，整体呈"之"字形（zigzag）。该题在仓库主 README.md 的题目列表中标记为 Medium 难度。

二、解题思路：把矩阵想象成 X/Y 坐标轴

原题解文档给出的核心思路是用模拟的方式直接遍历，解题关键在于"判断下一个位置"。将矩阵想象成一个 X/Y 坐标轴（X 轴向右，Y 轴向下），那么每次移动可分为两大类情况：

情况 1：斜角向右上遍历（东北方向）

• 当右上角在坐标轴内：正常计算，即x + 1（X 轴向右移动），y - 1（Y 轴向上移动）；
• 当右上角在坐标轴外（越界）：当前位置只能在第一行（X 轴上边界）或者最后一列（Y 轴右边界），此时需要判断该两种情况：应该让 X 坐标往右（即移动到下一行的起始列），或者 Y 坐标往上（即移动到下一列的起始行）。

情况 2：斜角向左下遍历（西南方向）

• 当左下角在坐标轴内：正常计算，即x - 1（X 轴向左移动），y + 1（Y 轴向下移动）；
• 当左下角在坐标轴外（越界）：当前位置只能在第一列（Y 轴左边界）或者最后一行（X 轴下边界），此时需要判断该两种情况：应该让 X 坐标往左，或者 Y 坐标往下。

也就是说，四个"角落出口"（上边界、下边界、左边界、右边界）是模拟遍历中最容易出错的地方——对角线一旦走出矩阵，就必须"换一条对角线"并反转方向重新进入矩阵。

三、仓库源码实现：解法一（方向数组法）

LeetCode-Go 仓库为本题提供了两种实现，见 498. Diagonal Traverse.go。解法一findDiagonalOrder1采用方向数组 + 越界回退的写法，代码最为精炼：

func findDiagonalOrder1(matrix [][]int) []int { if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 { return nil } row, col, dir, i, x, y, d := len(matrix), len(matrix[0]), [2][2]int{ {-1, 1}, {1, -1}, }, 0, 0, 0, 0 total := row * col res := make([]int, total) for i < total { for x >= 0 && x < row && y >= 0 && y < col { res[i] = matrix[x][y] i++ x += dir[d][0] y += dir[d][1] } d = (d + 1) % 2 if x == row { x-- y += 2 } if y == col { y-- x += 2 } if x < 0 { x = 0 } if y < 0 { y = 0 } } return res }

实现要点拆解

• 方向表：dir是一个[2][2]int数组，dir[0] = {-1, 1}表示向上右（东北）方向，dir[1] = {1, -1}表示向下左（西南）方向；d在 0 与 1 之间通过(d+1) % 2切换，实现方向的交替翻转。
• 内层循环：只要坐标(x, y)落在矩阵范围内就持续沿当前方向前进并写入结果，一旦越界立即跳出。
• 越界回退（关键）：跳出后坐标比实际多走了一步，因此需要回退。四种边界分别处理：
  • x == row（越出下边界）：x--回退一行，同时y += 2把列修正到新对角线的起点；
  • y == col（越出右边界）：y--回退一列，同时x += 2把行修正到新对角线的起点；
  • x < 0（越出上边界）：直接归零回x = 0；
  • y < 0（越出左边界）：直接归零回y = 0。
• 初始化：total := row * col，用make([]int, total)预分配结果切片，避免动态扩容，整体性能更优。

四、仓库源码实现：解法二（边界状态机法）

解法二findDiagonalOrder采用状态机 + 边界分支的思路，通过dir变量记录遍历状态：dir = 0代表从右上到左下的方向，dir = 1代表从左下到右上的方向，dir = -1代表上一次转变了方向（用于触发边界重定位）：

func findDiagonalOrder(matrix [][]int) []int { if len(matrix) == 0 { return []int{} } if len(matrix) == 1 { return matrix[0] } m, n, i, j, dir, res := len(matrix), len(matrix[0]), 0, 0, 0, []int{} for index := 0; index < m*n; index++ { if dir == -1 { if (i == 0 && j < n-1) || (j == n-1) { // 上边界和右边界 i++ if j > 0 { j-- } dir = 0 addTraverse(matrix, i, j, &res) continue } if (j == 0 && i < m-1) || (i == m-1) { // 左边界和下边界 if i > 0 { i-- } j++ dir = 1 addTraverse(matrix, i, j, &res) continue } } // 起点 (0,0) 与四条边界的重定位逻辑 if i == 0 && j == 0 { res = append(res, matrix[i][j]) if j < n-1 { j++ dir = -1 addTraverse(matrix, i, j, &res) continue } else { if i < m-1 { i++ dir = -1 addTraverse(matrix, i, j, &res) continue } } } if i == 0 && j < n-1 { // 上边界 j++ dir = -1 addTraverse(matrix, i, j, &res) continue } if j == 0 && i < m-1 { // 左边界 i++ dir = -1 addTraverse(matrix, i, j, &res) continue } if j == n-1 { // 右边界 if i < m-1 { i++ dir = -1 addTraverse(matrix, i, j, &res) continue } } if i == m-1 { // 下边界 j++ dir = -1 addTraverse(matrix, i, j, &res) continue } if dir == 1 { i-- j++ addTraverse(matrix, i, j, &res) continue } if dir == 0 { i++ j-- addTraverse(matrix, i, j, &res) continue } } return res } func addTraverse(matrix [][]int, i, j int, res *[]int) { if i >= 0 && i <= len(matrix)-1 && j >= 0 && j <= len(matrix[0])-1 { *res = append(*res, matrix[i][j]) } }

实现要点拆解

• 特判先行：空矩阵直接返回空切片；单行矩阵直接原样返回该行，天然规避退化场景。
• 边界分支全覆盖：代码依次处理了起点(0,0)、上边界、左边界、右边界、下边界五种位置，每种情况都重置dir = -1以触发下一轮的方向判定，从而完成"换对角线 + 反转方向"。
• 安全写入：辅助函数addTraverse在追加元素前再次检查i、j是否落在矩阵范围内，为状态机的复杂跳转提供兜底保护，这也是"防越界"的最后一层保险。

两种解法对比：解法一以"方向数组 + 越界回退"取胜，代码短、思路直白；解法二以"边界状态机"取胜，逻辑显式、易读但分支较多。两者均满足题目要求的时间复杂度 O(M x N)。

五、边界条件与测试验证

原题解文档特别强调：需要注意的边界条件包括二维数组为空、二维数组退化为一行或一列、退化为一个元素，具体例子见测试用例。仓库的测试文件 498. Diagonal Traverse_test.go 用表驱动测试完整覆盖了这些退化场景：

测试函数Test_Problem498以question498结构体组织参数（para498.one）与期望答案（ans498.one），对每个用例同时调用findDiagonalOrder与findDiagonalOrder1两种实现做断言比对，任一用例失败即通过t.Fatalf终止。这套用例直接印证了原题解文档强调的边界要点：非方阵（行数 ≠ 列数）时对角线会在底部或右侧"触底反弹"，必须依赖边界分支正确处理。

六、复杂度分析

• 时间复杂度：O(M x N)。每个元素恰好被访问并写入结果一次，内层循环虽会"多走一步越界"再回退，但整体访问次数仍与元素总数线性相关。
• 空间复杂度：O(M x N)（结果切片本身）外加 O(1) 的临时变量。解法一使用预分配的make([]int, total)，解法二使用动态append，两者空间开销同阶。

题目约束"元素总数不超过 10,000"意味着最坏情况下结果切片约含 10,000 个整数，两种实现的内存占用都在可接受范围内。

七、如何在仓库中阅读与运行

• 阅读题解：完整题目描述与解题思路见 leetcode/0498.Diagonal-Traverse/README.md。
• 查看源码：两种 Go 实现位于 498. Diagonal Traverse.go，函数签名均为findDiagonalOrder(matrix [][]int) []int。
• 运行测试：在仓库根目录执行go test ./leetcode/0498.Diagonal-Traverse/ -v -run Test_Problem498，即可看到表驱动用例逐条执行并验证两种解法的输出；仓库go.mod声明 Go 1.19 环境，主 README.md 中亦有整仓库的测试与覆盖说明（项目描述为 100% test coverage）。

八、延伸思考

对角线遍历是矩阵类题目的经典入门题，掌握了本题的"方向数组 + 边界回退"范式后，可继续挑战仓库中的同类矩阵遍历问题：

• 1329. Sort the Matrix Diagonally：对每条对角线分别排序，同样需要按i - j或i + j分组对角线；
• 1572. Matrix Diagonal Sum：求主副对角线和，是本题坐标运算的简化应用；
• 1424. Diagonal Traverse II 在仓库题目列表中出现但暂未收录实现，可作为进阶练习：其对角线数量可达 10^5，需要按对角线编号分组而非模拟单条路径。

理解对角线方向与"换行换列"的关系（x == row时x--; y += 2，y == col时y--; x += 2）是本类题目的通用钥匙，面试中如遇到变体（如从任意起点开始、改为蛇形顺序），均可基于本文的坐标轴模型快速推导。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go