矩阵题解——螺旋矩阵【LeetCode】

54. 螺旋矩阵

 1.1 核心思想

• 问题描述：给定一个二维矩阵，按照顺时针螺旋顺序返回所有元素。
• 解决思路：
  1. 定义四个边界：left、right、up、down，分别表示当前螺旋遍历的左、右、上、下边界。
  2. 定义四个方向：(0, 1)（向右）、(1, 0)（向下）、(0, -1)（向左）、(-1, 0)（向上）。
  3. 按照当前方向遍历矩阵，当到达边界时，调整边界并切换到下一个方向。
  4. 重复上述过程，直到遍历完所有元素。

1.2 具体步骤

1. 初始化：
   • 检查矩阵是否为空，如果为空则直接返回空列表。
   • 获取矩阵的行数 M 和列数 N。
   • 初始化四个边界：left = 0、right = N - 1、up = 0、down = M - 1。
   • 初始化结果列表 res。
   • 初始化当前位置 (x, y) 为 (0, 0)。
   • 初始化当前方向 cur_d 为 0（向右）。
2. 螺旋遍历：
   • 将当前元素 matrix[x][y] 添加到结果列表 res 中。
   • 检查是否需要切换方向：

     • 如果当前方向是向右（cur_d == 0）且到达右边界（y == right），则切换到向下方向（cur_d = 1），并将上边界 up 加 1。
     • 如果当前方向是向下（cur_d == 1）且到达下边界（x == down），则切换到向左方向（cur_d = 2），并将右边界 right 减 1。
     • 如果当前方向是向左（cur_d == 2）且到达左边界（y == left），则切换到向上方向（cur_d = 3），并将下边界 down 减 1。
     • 如果当前方向是向上（cur_d == 3）且到达上边界（x == up），则切换到向右方向（cur_d = 0），并将左边界 left 加 1。

   • 更新当前位置 (x, y) 为下一个方向的位置。
   • 重复上述过程，直到结果列表 res 的长度等于矩阵元素总数 M * N。
3. 返回结果：
   • 返回结果列表 res。

class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:if not matrix or not matrix[0]: return []M, N = len(matrix), len(matrix[0])left, right, up, down = 0, N - 1, 0, M - 1res = []x, y = 0, 0dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]cur_d = 0while len(res) != M * N:res.append(matrix[x][y])if cur_d == 0 and y == right:cur_d += 1up += 1elif cur_d == 1 and x == down:cur_d += 1right -= 1elif cur_d == 2 and y == left:cur_d += 1down -= 1elif cur_d == 3 and x == up:cur_d += 1left += 1cur_d %= 4x += dirs[cur_d][0]y += dirs[cur_d][1]return res

2.1 时间复杂度

• 遍历矩阵：每个元素被访问一次，时间复杂度为 O(M * N)。

2.2 空间复杂度

• 结果列表：存储所有矩阵元素，空间复杂度为 O(M * N)。
• 额外变量：仅使用常数级别的额外空间（如边界变量、方向数组等），空间复杂度为 O(1)。
• 总空间复杂度：O(M * N)（主要由结果列表决定）。