螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
边界模拟：
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int top = 0;
int bottom = m - 1;
int left = 0;
int right = n - 1;
vector<int> ans;
while (top <= bottom && left <= right)
{
for (int j = left; j <= right; j++)
{
ans.push_back(matrix[top][j]);
}
top++;
for (int i = top; i <= bottom; i++)
{
ans.push_back(matrix[i][right]);
}
right--;
if (top <= bottom)
{
for (int j = right; j >= left; j--)
{
ans.push_back(matrix[bottom][j]);
}
bottom--;
}
if (left <= right)
{
for (int i = bottom; i >= top; i--)
{
ans.push_back(matrix[i][left]);
}
left++;
}
}
return ans;
}
};
核心思想
螺旋遍历的本质，是一圈一圈地访问矩阵。
每一圈的顺序固定为：
- 从左到右走上边界。
- 从上到下走右边界。
- 从右到左走下边界。
- 从下到上走左边界。
走完一圈以后，这一圈已经全部访问过。
接下来只需要把边界向内收缩一层，继续处理下一圈。
所以我们用四个变量表示当前还没有访问的矩形区域：
top：当前上边界bottom：当前下边界left：当前左边界right：当前右边界
只要满足：
top <= bottom && left <= right
说明还有元素没有访问。
四个边界的含义
初始时：
int top = 0;
int bottom = m - 1;
int left = 0;
int right = n - 1;
这表示整个矩阵都还没有被遍历。
访问完上边界以后：
top++;
说明原来的上边界已经访问完，下一圈的上边界向下移动一行。
访问完右边界以后：
right--;
说明原来的右边界已经访问完，下一圈的右边界向左移动一列。
访问完下边界以后：
bottom--;
说明原来的下边界已经访问完，下一圈的下边界向上移动一行。
访问完左边界以后：
left++;
说明原来的左边界已经访问完，下一圈的左边界向右移动一列。
每一圈怎么遍历
假设当前未访问区域是：
top ... bottom
和：
left ... right
1. 从左到右访问上边界
固定行号 top，列号从 left 到 right：
for (int j = left; j <= right; j++)
{
ans.push_back(matrix[top][j]);
}
top++;
2. 从上到下访问右边界
固定列号 right，行号从新的 top 到 bottom：
for (int i = top; i <= bottom; i++)
{
ans.push_back(matrix[i][right]);
}
right--;
这里使用新的 top，是因为旧的上边界已经访问过了。
3. 从右到左访问下边界
访问下边界前，需要先判断：
top <= bottom
如果不满足，说明已经没有下边界了。
满足时，固定行号 bottom，列号从 right 到 left：
if (top <= bottom)
{
for (int j = right; j >= left; j--)
{
ans.push_back(matrix[bottom][j]);
}
bottom--;
}
4. 从下到上访问左边界
访问左边界前，需要判断：
left <= right
如果不满足，说明已经没有左边界了。
满足时，固定列号 left，行号从 bottom 到 top：
if (left <= right)
{
for (int i = bottom; i >= top; i--)
{
ans.push_back(matrix[i][left]);
}
left++;
}
为什么需要额外判断
这题最容易出错的地方，是矩阵剩下最后一行或者最后一列时，可能会重复访问。
例如：
matrix = [[1,2,3]]
只有一行。
从左到右访问上边界后，top 会增加。
此时已经没有下边界了。
如果不判断 top <= bottom，再去从右到左访问下边界，就会把同一行重复加入答案。
同理，如果矩阵只剩一列，也可能重复访问左边界。
所以在访问下边界和左边界之前，必须分别判断：
top <= bottom
和：
left <= right
这样可以保证每个元素只被访问一次。
正确性证明
我们证明算法返回的数组正好是矩阵的顺时针螺旋遍历结果。
结论 1：每一圈的访问顺序正确
在某一轮循环中，当前未访问区域由四个边界确定：
top, bottom, left, right
算法依次访问：
- 上边界：从左到右
- 右边界：从上到下
- 下边界：从右到左
- 左边界：从下到上
这正好就是顺时针访问当前外圈的顺序。
所以每一圈的访问顺序正确。
结论 2：访问完一圈后，边界会正确收缩
访问完上边界后，top++。
访问完右边界后，right--。
访问完下边界后，bottom--。
访问完左边界后，left++。
因此已经访问过的外圈会被排除在下一轮循环之外。
下一轮循环处理的正好是内部剩余矩形。
所以边界收缩正确。
结论 3：每个元素只会被访问一次
每次访问一条边界后，都会立即把对应边界向内收缩。
后续循环不会再访问已经收缩出去的边界。
同时，在访问下边界和左边界前，算法会检查当前区域是否仍然存在对应边界。
所以单行、单列的情况不会被重复访问。
因此每个元素最多被访问一次。
结论 4：所有元素都会被访问
只要：
top <= bottom && left <= right
就说明当前仍然存在一个未访问的矩形区域。
算法会访问这个区域的外圈，并继续向内收缩。
当循环结束时，说明：
top > bottom
或者：
left > right
此时已经不存在未访问区域。
所以所有元素都会被访问。
得出结论
由结论 1 可知，算法每一圈的访问顺序符合顺时针螺旋顺序。
由结论 2 可知，算法会逐层向内处理矩阵。
由结论 3 可知，算法不会重复访问元素。
由结论 4 可知，算法不会漏掉元素。
因此算法返回的结果正确。
举例理解
以：
matrix = [[1,2,3],
[4,5,6],
[7,8,9]]
为例。
第一圈：
- 上边界：
1, 2, 3 - 右边界：
6, 9 - 下边界：
8, 7 - 左边界：
4
此时答案是：
[1,2,3,6,9,8,7,4]
边界向内收缩后，只剩中间：
5
继续访问，最终得到：
[1,2,3,6,9,8,7,4,5]
复杂度分析
矩阵中每个元素都会被访问一次，且只访问一次。
所以时间复杂度是：
O(mn)
其中 m 是矩阵行数，n 是矩阵列数。
除了返回数组 ans 以外，只使用了四个边界变量。
所以额外空间复杂度是：
O(1)
如果把返回数组也计入空间，则空间复杂度是 O(mn)。