498 对角线遍历

题目描述#

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

知识边界#

对角线坐标特性：在二维矩阵中，同一条对角线（右上到左下方向）上的元素的行列坐标索引之和 i + j 是一个固定常数。
切片预分配：在 Go 语言中，通过 make([]int, 0, m*n) 预先分配切片的底层数组容量，可以避免在 append 操作时因容量不足导致的内存重新分配与数组拷贝，从而优化性能。
Go 1.21+ 内置函数：min 和 max 函数在 Go 1.21 版本中已成为内置函数，可直接对多种数值类型使用，避免了以往需要调用 math.Min 并进行 float64 类型转换的繁琐。

思路#

矩阵大小为 $m \times n$，行索引 $i \in [0, m-1]$，列索引 $j \in [0, n-1]$。

关键在于发现对角线的数学规律：对于任意一条对角线（沿右上到左下方向），其上任意元素的横纵坐标之和 $d = i + j$ 均为定值。矩阵的左上角起点为 $d = 0+0 = 0$，右下角终点为 $d = (m-1) + (n-1) = m + n - 2$。因此总共有 $m + n - 1$ 条对角线。

针对每一条对角线（固定数值 $d$），我们需要确定行坐标 $i$ 的合法范围，以及遍历的方向：

行坐标范围：必须同时满足 $0 \le i \le m-1$ 以及 $0 \le j \le n-1$。将 $j = d - i$ 代入后，得出 $0 \le d - i \le n - 1$，从而推导出 $i \ge d - n + 1$。综合这两个条件，行坐标 $i$ 的下界为 max(0, d - (n - 1))，上界为 min(d, m - 1)。
遍历方向：
- 当 $d$ 为偶数时，对角线是自左下向右上遍历，行索引 $i$ 是递减的。所以循环从上限 min(d, m-1) 开始，递减到下限 max(0, d-(n-1))。
- 当 $d$ 为奇数时，对角线是自右上向左下遍历，行索引 $i$ 是递增的。所以循环从下限 max(0, d-(n-1)) 开始，递增到上限 min(d, m-1)。

时间复杂度：$O(m \times n)$。矩阵中的每个元素仅被访问一次并直接加入结果数组。 空间复杂度：$O(1)$。除了用于存放结果的数组外，只需要常数级别的变量来控制遍历，不占用额外的辅助内存空间。

代码#

func findDiagonalOrder(mat [][]int) []int {
	m, n := len(mat), len(mat[0])
	res := make([]int, 0, m*n)
	
	// d = i + j (代表每一条对角线)
	// 左上角 d = 0, 右下角 d = m + n - 2
	for d := 0; d < m+n-1; d++ {
		if d%2 == 0 {
			// d为偶数，自左下向右上遍历，行坐标 i 递减
			for i := min(d, m-1); i >= max(0, d-(n-1)); i-- {
				res = append(res, mat[i][d-i])
			}
		} else {
			// d为奇数，自右上向左下遍历，行坐标 i 递增
			for i := max(0, d-(n-1)); i <= min(d, m-1); i++ {
				res = append(res, mat[i][d-i])
			}
		}
	}
	
	return res
}