各位题友大家好！今天是 @负雪明烛 坚持日更的第 50 天。今天力扣上的每日一题是「54. 螺旋矩阵」。

解题思路

题意是要我们螺旋向内遍历矩阵，力扣上类似地按照一定规则打印矩阵的题目有好几个。我觉得需要考虑以下几个问题：

起始位置
2. 移动方向
3. 边界
4. 结束条件

今天这个题目只要把上面几个问题想清楚了，起始不难。

1. 起始位置

螺旋矩阵的遍历起点是矩阵的左上角，也就是 (0, 0) 位置。

2. 移动方向

起始位置的下一个移动方向是向右。在遍历的过程中，移动方向是固定的：

右 → ，下↓，左←，上↑

移动方向是按照上面的顺序循环进行的。只有当移动到了边界，才会更改方向。

3. 边界

本题的边界是最大的难点，因为是随着遍历的过程而变化的。螺旋遍历的时候，已经遍历的数字不能再次遍历，所以边界会越来越小。

我发现的规则是：如果当前行（列）遍历结束之后，就需要把这一行（列）的边界向内移动一格。

以下面的图为例， up, down, left, right 分别表示四个方向的边界。如果我们把第一行遍历结束（到了右边界），此时需要修改移动方向、并且把上边界 up 下移一行。

当绕了一圈后，从下向上走到 up 边界的时候，同样根据 up 判断边界。

由此可见，根据维护的四个方向的边界，就知道什么时候更改移动方向了。

4. 结束条件

螺旋遍历的结束条件是所有的位置都被遍历到。

代码

下面的代码不难：

up, down, left, right 分别表示四个方向的边界。
- x, y 表示当前位置。
dirs 分别表示移动方向是 右、下、左、上 。
cur_d 表示当前的移动方向的下标，dirs[cur_d] 就是下一个方向需要怎么修改 x, y。
cur_d == 0 and y == right 表示当前的移动方向是向右，并且到达了右边界，此时将移动方向更改为向下，并且上边界 up 向下移动一格。

结束条件是结果数组 res 的元素个数能与 matrix 中的元素个数。

class Solution(object):
  def spiralOrder(self, matrix):
      """
      :type matrix: List[List[int]]
      :rtype: 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 - 1
      res = []
      x, y = 0, 0
      dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
      cur_d = 0
      while len(res) != M * N:
          res.append(matrix[x][y])
          if cur_d == 0 and y == right:
              cur_d += 1
              up += 1
          elif cur_d == 1 and x == down:
              cur_d += 1
              right -= 1
          elif cur_d == 2 and y == left:
              cur_d += 1
              down -= 1
          elif cur_d == 3 and x == up:
              cur_d += 1
              left += 1
          cur_d %= 4
          x += dirs[cur_d][0]
          y += dirs[cur_d][1]
      return res

时间复杂度：$O(M * N)$
空间复杂度：$O(M * N)$，如果不把结果计算在内，那么空间复杂度为 $O(1)$

刷题心得

这种遍历的问题，本身其实不难，容易出错的地方在于移动方向、边界等处理。细节是魔鬼，刷题经验多了，对细节的处理也会更好一些。

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】54. 螺旋矩阵