最外层所有元素按照顺时针顺序输出，其次是次外层，以此类推。
我们定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。

题目

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例

示例 1:

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

示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

测试用例

数组中有多行多列；数组中只有一行；数组中只有一列；数组中只有一行一列。

本题考点

本题主要考查应聘者的思维能力。从外到内顺时针打印矩阵这个过程非常复杂，应聘者如何能很快地找出其规律并写出完整的代码，是解这道题的关键。当问题比较抽象不容易理解时，可以试着画几幅图形帮助理解，这样往往能更快地找到思路。

考察知识点

数组

核心思想

最外层所有元素按照顺时针顺序输出，其次是次外层，以此类推。

我们定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如，下图矩阵最外层元素都是第 1 层，次外层元素都是第 2 层，然后是第 3 层的。

[[1, 1, 1, 1, 1, 1, 1],
 [1, 2, 2, 2, 2, 2, 1],
 [1, 2, 3, 3, 3, 2, 1],
 [1, 2, 2, 2, 2, 2, 1],
 [1, 1, 1, 1, 1, 1, 1]]

对于每层，我们从左上方开始以顺时针的顺序遍历所有元素，假设当前层左上角坐标是 \(\text{(r1, c1)}\)，右下角坐标是 \(\text{(r2, c2)}\)。

首先，遍历上方的所有元素 \(\text{(r1, c)}\)，按照 \(\text{c = c1,...,c2}\) 的顺序。然后遍历右侧的所有元素 \(\text{(r, c2)}\)，按照 \(\text{r = r1+1,...,r2}\) 的顺序。如果这一层有四条边（也就是 \(\text{r1 < r2}\) 并且 \(\text{c1 < c2}\) ），我们以下图所示的方式遍历下方的元素和左侧的元素。

算法

特判matrix为空的情况，直接返回[]。
声明 r1 为行起点 0，r2 为行终点 len(matrix) 。
声明 c1 为列起点 0，c2 为列终点 len(matrix[0]) - 1 。
进入 while 循环，一次 while 循环，就是一层（top、left、bottom、right），终止条件是 r1 > r2 and c1 > c2，如果满足终止条件，就说明最里面一层也循环。
- for 循环，调用迭代函数 spiral_coords 处理 r1, c1, r2, c2。
- 更新行，行起点（r1）增加，行终点（r2）减小。这样就把已经遍历了的right和left给去掉了。
- 更新列，列起点（c1）增加，列终点（c2）减小。这样就把已经遍历了的top和bottom给去掉了。
return ans
声明 spiral_coords(r1, c1, r2, c2)函数，根据传入的行和列的起点和终点，分离相应的坐标。
- 首先循环 top，特点是行不变，列变化， c 从 c1 变化到 c2，yield r1, c。
- 然后循环 right，特点是列不变，行变化，r 从 r1 变化到 r2，yield r, c2。
- 接着判断当前位置，如果满足条件，r1 < r2 and c1 < c2，则说明还没结束，还有bottom和left可以遍历。
  - 循环bottom，特点是行不变，列变化，c 从 c2+1 变化到 c1+1，yield r2, c。
  - 循环left，特点是列不变，行变化，r 从 r2+1 变化到 r1+1，yield r, c1。

LeetCode题解

Python版本

class Solution(object):
    def spiralOrder(self, matrix):
        def spiral_coords(r1, c1, r2, c2):  # 由于spiral_coords使用了yield进行了返回，就变成了一个迭代器。
            for c in range(c1, c2 + 1):  # 首先循环top，特点是行不变，列变化， c从c1变化到c2。
                yield r1, c  # 使用了yield返回 如果这次yield出去c=1，则下次进来循环时就会接着上次c先自增为2，再yield出去，以此类推。
            for r in range(r1 + 1, r2 + 1):  # 然后循环right，特点是列不变，行变化，从r1变化到r2。
                yield r, c2
            if r1 < r2 and c1 < c2:  # 接着判断当前位置，如果满足条件，r1 < r2 and c1 < c2，则说明还没结束，还有bottom和left可以遍历。
                for c in range(c2 - 1, c1, -1):  # 循环bottom，特点是行不变，列变化，从c2-1变化到c1+1。
                    yield r2, c
                for r in range(r2, r1, -1):  # 循环left，特点是列不变，行变化，从r2-1变化到r1+1。
                    yield r, c1

        if not matrix: return []  # 特判matrix为空的情况，直接返回[]
        ans = []  # 声明ans
        r1, r2 = 0, len(matrix) - 1  # 声明r1为行起点0，r2为行终点len(matrix)。
        c1, c2 = 0, len(matrix[0]) - 1  # 声明c1为列起点，c2为列终点len(matrix[0]) - 1
        while r1 <= r2 and c1 <= c2:  # 进入while循环，一次while循环，就是一层（top、left、bottom、right）
            for r, c in spiral_coords(r1, c1, r2, c2):  # 调用spiral_coords函数处理r1，c1，r2，c2。
                ans.append(matrix[r][c])  # 将调用得到的坐标对应的数值放进ans
            r1 += 1; r2 -= 1  # 更新行，行起点（r1）增加，行终点（r2）减小。 这样就把已经遍历了的right和left给去掉了。
            c1 += 1; c2 -= 1  # 更新列，列起点（c1）增加，列终点（c2）减小。这样就把已经遍历了的top和bottom给去掉了。
        return ans

print("leet code accept!!!")
Input = [
    [
        [ 1, 2, 3 ],
        [ 4, 5, 6 ],
        [ 7, 8, 9 ]
    ],
    [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9,10,11,12]
    ]
]
Input1 = [10]
Answer = [
    [1,2,3,6,9,8,7,4,5],
    [1,2,3,4,8,12,11,10,9,5,6,7]
]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.spiralOrder(Input[i])
        print(reslut == Answer[i])

时间复杂度： \(O(N)\)，其中 N 是输入矩阵所有元素的个数。因为我们将矩阵中的每个元素都添加进答案里。
空间复杂度： \(O(N)\)，需要矩阵 ans 存储信息。
执行用时 :52 ms, 在所有 Python3 提交中击败了11.14%的用户。
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了18.94%的用户。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.size()==0 || matrix[0].size()==0){
            return {};
        }

        vector<int> order;
        int rows=matrix.size(), colums=matrix[0].size();
        int left=0, right=colums-1, top=0, bottom=rows-1;
        while(left<=right && top <= bottom){
            for(int column=left; column<=right; column++){  // 首先循环top，特点是行不变，列变化， ccolumn从left变化到right。
                order.push_back(matrix[top][column]);
            }
            for(int row=top+1; row<=bottom; row++){  // 然后循环right，特点是列不变，行变化，从top变化到bottom。
                order.push_back(matrix[row][right]);
            }
            if(left<right && top<bottom){  // 接着判断当前位置，如果满足条件，left < right and top < bottom，则说明还没结束，还有bottom和left可以遍历。
                for(int column=right-1; column>left; column--){  // 循环bottom，特点是行不变，列变化，从right-1变化到left+1。
                    order.push_back(matrix[bottom][column]);
                }
                for(int row=bottom; row>top; row--){  // 循环left，特点是列不变，行变化，从bottom变化到top+1。
                    order.push_back(matrix[row][left]);
                }
            }
            // 向中间收缩
            left++;  // left+1
            right--;  // right-1
            top++;  // top-1
            bottom--;  // bottom-1
        }
        return order;
    }
};

int main(){
    cout << "hello world" << endl;
    vector<vector<int>> input = {{1,2,3},{4,5,6},{7,8,9}};
    Solution so;
    vector<int> res;
    res = so.spiralOrder(input);
    for(int i=0; i<res.size(); i++){
        cout << res[i] << endl;
    }
    int a;
    cin >> a;
}

有效语法糖

1、python中 yield 的用法

参考连接

什么是yield？一个将普通函数变成迭代器的关键字。

首先，可以将 yield 视作 return，是在程序中返回某个值，返回之后程序就不再往下运行了。其次，做一个是生成器（generator）的一部分（带yield的函数才是真正的迭代器）。

def foo():
    print("starting...")
    while True:
        res = yield 4  # 第一次调用next(g)，再这里就停止了。
        print("res:",res)  # 第二次调用next(g)，紧接着从这一行开始执行。
g = foo()  # 程序开始执行以后，因为foo函数中有yield关键字，所以foo函数并不会真的执行，而是先得到一个生成器g(相当于一个对象)
print(next(g))  # 直到调用next方法，foo函数正式开始执行，先执行foo函数中的print方法，然后进入while循环。
print("*"*20)
print(next(g))  #  开始执行这个print(next(g)),这个时候和上面那个差不多，不过不同的是，这个时候是从刚才那个next程序停止的地方开始执行的，也就是要执行res的赋值操作，这时候要注意，这个时候赋值操作的右边是没有值的（因为刚才那个是return出去了，并没有给赋值操作的左边传参数），所以这个时候res赋值是None,所以接着下面的输出就是res:None。
````

输出

```python
starting...
4  # 把yield想想成return,return了一个4之后，程序停止，并没有执行赋值给res操作，此时next(g)语句执行完成，所以输出的前两行（第一个是while上面的print的结果,第二个是return出的结果）是执行print(next(g))的结果，也就是输出 4。
********************  # 程序执行print("*"*20)，输出20个*
res: None
4  # 输出 res: None之后，程序会继续在while里执行，又一次碰到yield,这个时候同样return 出4，然后程序停止，print函数输出的4就是这次return出的4。

注意，第二次 print(next(g)) 是在第一次 print(next(g)) 执行之后再执行的，不过不同的是，这个时候是从刚才那个next程序停止的地方开始执行的，也就是要执行res的赋值操作。

yield 的含义：带yield的函数是一个生成器，而不是一个函数了，这个生成器有一个函数就是 next 函数，next就相当于“下一步”生成哪个数，这一次的 next 开始的地方是接着上一次的 next 停止的地方执行的，所以调用 next 的时候，生成器并不会从 foo 函数的开始执行，只是接着上一步停止的地方开始，然后遇到 yield后，return 出要生成的数，此步就结束。

那么，如何向带有 yield 的函数传递参数？

def foo():
    print("starting...")
    while True:
        res = yield 4
        print("res:",res)  # send(7)调用，等于先设置res=7，再执行 print("res:",res)。
g = foo()
print(next(g))
print("*"*20)
print(g.send(7))

再看一个这个生成器的send函数的例子，这个例子就把上面那个例子的最后一行换掉了，输出结果：

starting...
4
********************
res: 7
4

send 是发送一个参数给 res 的，因为上面讲到，return的时候，并没有把4赋值给 res，下次执行的时候只好继续执行赋值操作，只好赋值为None了，而如果用 send 的话，开始执行的时候，先接着上一次（return 4之后）执行，先把7赋值给了 res，然后执行 next 的作用，遇见下一回的 yield ，return出结果后结束。

为什么要用 yield ？可以灵活的将函数改成迭代器。比如说取 0,1,2,3,4,5,6,7,8,9,10 1). 使用range迭代器

1
2
3

print("staring...")
for i in range(10):
	print(i)

输出

staring...
0
1
2
3
4
5
6
7
8
9

2). 使用 yield 设计迭代器

def foo(num, target):
    print("staring...")
    while num < target-1:
        num += 1
        yield num

for n in foo(-1, 10):
    print(n)

输出

staring...
0
1
2
3
4
5
6
7
8
9

LeetCode 剑指offer

数组与指针

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LeetCode 55. 跳跃游戏（中）上一篇

LeetCode 53. 最大子序和（易）& 剑指offer 面试题42. 连续子数组的最大和（易）下一篇

LeetCode 54. 螺旋矩阵（中）& 剑指offer 面试题29. 顺时针打印矩阵（易）

题目

示例

考察知识点

核心思想

Python版本

C++版本

有效语法糖