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

解题思路

题意仍然是要我们螺旋向内遍历矩阵，遍历的过程中依次放入 1~N^2 等各个数字，和昨天的题目 54. 螺旋矩阵一模一样。我觉得需要考虑以下几个问题：

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

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

1. 起始位置

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

2. 移动方向

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

$【每日一题】59. 螺旋矩阵 II - 图1$

移动方向是按照上面的顺序循环进行的。每次当移动到了边界，才会更改方向。但边界并不是固定的，请看下面分析。

3. 边界

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

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

下面用两种不同的方法来标记边界。

3.1 四个变量标记边界

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

【每日一题】59. 螺旋矩阵 II - 图2

当绕了一圈后，从下向上走到 新up 边界的时候，此时需要修改新的移动方向为向右、并且把左边界 left 下移一格，即从 旧 left 位置移动到 新 left 位置。

【每日一题】59. 螺旋矩阵 II - 图3

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

3.2 使用非 0 数字标记边界

结合题目给出的要求，我们在遍历的过程中，需要依次放入 $1~N^2$ 数字，如果我们把结果数组的所有位置初始化为 0，那么非 0 的位置就代表我们已经遍历过了。

也就是说，当遍历到数组的原始边界或者撞到了非 0 的数字，表示当前方向已经遍历结束，需要更改移动方向。这个做法的优点是省去了维护 4 个变量表示的边界。

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 generateMatrix(self, n):
        if n == 0: return []
        res = [[0] * n for i in range(n)]
        left, right, up, down = 0, n - 1, 0, n - 1
        x, y = 0, 0
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        cur_d = 0
        count = 0
        while count != n * n:
            res[x][y] = count + 1
            count += 1
            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

时间复杂度： $【每日一题】59. 螺旋矩阵 II - 图4$ #card=math&code=O%28M%20%2A%20N%29)
空间复杂度： $【每日一题】59. 螺旋矩阵 II - 图5$ #card=math&code=O%28M%20%2A%20N%29)，如果不把结果计算在内，那么空间复杂度为 $【每日一题】59. 螺旋矩阵 II - 图6$ #card=math&code=O%281%29)

使用非 0 数字标记边界

下面的代码更简洁，初始移动方向是向右，如果遇到了数组边界或者遇到了非 0 的数字，那么就要转动方向。转向的方法是 cur_d = (cur_d + 1) % 4 ，cur_d 表示了当前的方向是 directions 中的哪个，顺序依次是右、下、左、上。

class Solution(object):
    def generateMatrix(self, n):
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        res = [[0] * n for i in range(n)]
        x, y = 0, 0
        count = 0
        cur_d = 0
        while count != n * n:
            res[x][y] = count + 1
            count += 1
            dx, dy = directions[cur_d][0], directions[cur_d][1]
            newx, newy = x + dx, y + dy
            if newx < 0 or newx >= n or newy < 0 or newy >= n or res[newx][newy] != 0:
                cur_d = (cur_d + 1) % 4
                dx, dy = directions[cur_d][0], directions[cur_d][1]
            x, y = x + dx, y + dy
        return res

时间复杂度： $【每日一题】59. 螺旋矩阵 II - 图7$ #card=math&code=O%28M%20%2A%20N%29)
空间复杂度： $【每日一题】59. 螺旋矩阵 II - 图8$ #card=math&code=O%28M%20%2A%20N%29)，如果不把结果计算在内，那么空间复杂度为 $【每日一题】59. 螺旋矩阵 II - 图9$ #card=math&code=O%281%29)

刷题心得
每个定义的变量都有其具体的含义，需要在遍历过程中根据其含义，维护其取值。一个变量也不能落下。
- 在代码中维护好了各变量的取值，是做对题目的基础。

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

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

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

【每日一题】59. 螺旋矩阵 II