Diagonal Traverse,LeetCode,498

题目描述：

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

示例：

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

解释:

解题思路：

1. 初始化：
   • 创建一个结果列表 result 用于存储遍历的元素。
   • 设置初始位置 (i, j) 为 (0, 0)，即矩阵的左上角。
   • 设置方向标志 direction，初始为 1 表示向右上遍历，-1 表示向左下遍历。
2. 遍历矩阵：
   • 使用一个循环，直到遍历完所有元素（即遍历了 M x N 次）。
   • 在每次循环中，将当前元素添加到 result 列表中。
   • 根据当前方向 direction 更新位置 (i, j)：
     • 如果 direction 为 1（向右上），则 i 减 1，j 加 1。
     • 如果 direction 为 -1（向左下），则 i 加 1，j 减 1。
   • 检查更新后的位置 (i, j) 是否越界：
     • 如果 i 越界（小于 或大于 M-1），则调整 i 并改变方向。
     • 如果 j 越界（小于 或大于 N-1），则调整 j 并改变方向。
3. 返回结果：
   • 遍历完成后，返回 result 列表。

代码实现（Python）：

class Solution: def findDiagonalOrder(self, matrix): if not matrix or not matrix[0]: return []

    M, N = len(matrix), len(matrix[0])
    result = []
    i, j = 0, 0
    direction = 1

    for _ in range(M * N):
        result.append(matrix[i][j])

        if direction == 1:
            new_i, new_j = i - 1, j + 1
            if new_i < 0 or new_j >= N:
                direction = -1
                if new_j >= N:
                    i += 1
                else:
                    j += 1
            else:
                i, j = new_i, new_j
        else:
            new_i, new_j = i + 1, j - 1
            if new_i >= M or new_j < 0:
                direction = 1
                if new_i >= M:
                    j += 1
                else:
                    i += 1
            else:
                i, j = new_i, new_j

    return result

解释：

• 初始化：检查矩阵是否为空，获取矩阵的行数 M 和列数 N，初始化结果列表 result，起始位置 (i, j) 和方向 direction。
• 遍历矩阵：使用一个循环遍历所有元素，根据当前方向更新位置，并在越界时调整位置和方向。
• 返回结果：遍历完成后，返回结果列表 result。

这个解法的时间复杂度为 O(M * N)，空间复杂度为 O(1)（不包括结果列表的空间）。

希望这个详细的解释和代码实现能帮助你理解并解决 LeetCode 498 题“对角线遍历”。如果有任何进一步的问题，欢迎继续提问！