LeetCode 498. 对角线遍历

Categories:

Tags:

题目描述
思路分析
1. 解法一：按对角线编号遍历（推荐）
相似题目

题目描述

✅ 498. 对角线遍历

思路分析

解法一：按对角线编号遍历（推荐）

核心思路：

位置 (i, j) 的对角线编号为 i + j。

偶数编号对角线从下到上遍历，奇数编号从上到下遍历。

依次收集即可。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 表示矩阵行列数。

空间复杂度：O(1)，除结果外仅常数空间。

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] res = new int[m * n];
        int idx = 0;

        for (int d = 0; d <= m + n - 2; d++) {
            if (d % 2 == 0) {
                int i = Math.min(d, m - 1);
                int j = d - i;
                while (i >= 0 && j < n) {
                    res[idx++] = mat[i][j];
                    i--;
                    j++;
                }
            } else {
                int j = Math.min(d, n - 1);
                int i = d - j;
                while (j >= 0 && i < m) {
                    res[idx++] = mat[i][j];
                    i++;
                    j--;
                }
            }
        }

        return res;
    }
}

func findDiagonalOrder(mat [][]int) []int {
	m := len(mat)
	n := len(mat[0])
	res := make([]int, 0, m*n)

	for d := 0; d <= m+n-2; d++ {
		if d%2 == 0 {
			i := d
			if i > m-1 {
				i = m - 1
			}
			j := d - i
			for i >= 0 && j < n {
				res = append(res, mat[i][j])
				i--
				j++
			}
		} else {
			j := d
			if j > n-1 {
				j = n - 1
			}
			i := d - j
			for j >= 0 && i < m {
				res = append(res, mat[i][j])
				i++
				j--
			}
		}
	}

	return res
}

相似题目

题目	难度	考察点
54. 螺旋矩阵	中等	矩阵遍历
59. 螺旋矩阵 II	中等	矩阵遍历
73. 矩阵置零	中等	矩阵遍历
48. 旋转图像	中等	矩阵操作
498. 对角线遍历	中等	矩阵遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/82262053