对角线遍历-LeetCode

对角线遍历

🎯 问题描述（来源于LeetCode）

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

• m == mat.length

• n == mat[i].length

• 1 <= m, n <= 104

• 1 <= m * n <= 104

• -105 <= mat[i][j] <= 105
  示例：

• 示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

• 示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

💻 解题思路

思路1：遍历

思路1：代码实现

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        if not mat or not mat[0]:
            return []
        m, n = len(mat), len(mat[0])
        ans = []
        row, col = 0, 0
        direction = 1  
        while len(ans) < m * n:
            ans.append(mat[row][col])
            if direction == 1:  
                new_row = row - 1
                new_col = col + 1
            else:  
                new_row = row + 1
                new_col = col - 1
            is_out_of_bounds = new_row < 0 or new_row >= m or new_col < 0 or new_col >= n
            if not is_out_of_bounds:
                row, col = new_row, new_col
            else:
                if direction == 1: 
                    if col + 1 < n:
                        col += 1
                    else:
                        row += 1
                else:  
                    if row + 1 < m:
                        row += 1
                    else:
                        col += 1
                direction *= -1
        return ans

思路1：📊 性能分析

提交结果

• 运行时间：13ms击败50.65%
• 内存消耗：19.50MB击败25.22%

复杂度验证

• 时间复杂度：$O(m*n)$
• 空间复杂度：$O(m*n)$

思考

记录遍历方向，越界反转