leetcode 面试经典 150 题：螺旋矩阵

题目

给你一个 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.length
  n == matrix[i].length
  1 <= m, n <= 10
  -100 <= matrix[i][j] <= 100

题解

1. 核心要点：解该题的关键在于维护四个边界变量，并在每遍历完一层后更新这些边界。通过这种方式，我们可以确保按照螺旋顺序遍历矩阵中的所有元素。
   • 初始化边界：
     top 和 bottom 分别初始化为矩阵的第一行和最后一行的索引。
     left 和 right 分别初始化为矩阵的第一列和最后一列的索引。
   • 循环条件：
     当 top 小于等于 bottom 且 left 小于等于 right 时，继续循环。这个条件确保了我们不会在矩阵遍历完成后继续执行。
   • 遍历顶部行：
     从 left 到 right 遍历 top 行，将元素添加到结果列表中。
     遍历完成后，将 top 索引加1，因为顶部行已经遍历完成。
   • 遍历右侧列：
     从 top 到 bottom 遍历 right 列，将元素添加到结果列表中。
     遍历完成后，将 right 索引减1，因为右侧列已经遍历完成。
   • 检查是否需要继续遍历：
     如果 top 小于等于 bottom，则说明还有底部行需要遍历。
     从 right 到 left 遍历 bottom 行，将元素添加到结果列表中。
     遍历完成后，将 bottom 索引减1。
   • 遍历左侧列：
     如果 left 小于等于 right，则说明还有左侧列需要遍历。
     从 bottom 到 top 遍历 left 列，将元素添加到结果列表中。
     遍历完成后，将 left 索引加1。
   • 返回结果：
     所有元素遍历完成后，返回结果列表。
2. 时间复杂度：O(mn)
3. 空间复杂度：O(1)
4. c++ 实现算法：

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> result;if (matrix.empty()) return result;int top = 0, bottom = matrix.size() - 1;int left = 0, right = matrix[0].size() - 1;while (top <= bottom && left <= right) {// 从左到右沿着最上面一行遍历for (int i = left; i <= right; ++i) {result.push_back(matrix[top][i]);}top++;  // 将顶部边界向下移动// 从上到下沿着最右列遍历。for (int i = top; i <= bottom; ++i) {result.push_back(matrix[i][right]);}right--;  //将右边界向左移动if (top <= bottom) {//从右向左沿着底部一行遍历for (int i = right; i >= left; --i) {result.push_back(matrix[bottom][i]);}bottom--;  //将底部边界向上移动}if (left <= right) {//从底向上沿着最左列遍历for (int i = bottom; i >= top; --i) {result.push_back(matrix[i][left]);}left++;  //将左边界向右移动}}return result;}
};

5. 演示：

/*
假设输入矩阵为：[ [ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]
]初始状态：
top = 0, bottom = 2, left = 0, right = 2
result = []（最终结果）第一步：从左到右遍历上边界
我们首先遍历矩阵的上边界，从左到右：
遍历 matrix[0][0] = 1, matrix[0][1] = 2, matrix[0][2] = 3，把它们添加到 result 中。
更新 result：[1, 2, 3]
增加 top，使 top = 1。
当前状态：
result = [1, 2, 3]
top = 1, bottom = 2, left = 0, right = 2第二步：从上到下遍历右边界
接下来遍历右边界，从上到下：
遍历 matrix[1][2] = 6，matrix[2][2] = 9，把它们添加到 result 中。
更新 result：[1, 2, 3, 6, 9]
减少 right，使 right = 1。
当前状态：
result = [1, 2, 3, 6, 9]
top = 1, bottom = 2, left = 0, right = 1第三步：从右到左遍历下边界
接下来遍历下边界，从右到左：
遍历 matrix[2][1] = 8, matrix[2][0] = 7，把它们添加到 result 中。
更新 result：[1, 2, 3, 6, 9, 8, 7]
减少 bottom，使 bottom = 1。
当前状态：
result = [1, 2, 3, 6, 9, 8, 7]
top = 1, bottom = 1, left = 0, right = 1第四步：从下到上遍历左边界
接下来遍历左边界，从下到上：
遍历 matrix[1][0] = 4，把它添加到 result 中。
更新 result：[1, 2, 3, 6, 9, 8, 7, 4]
增加 left，使 left = 1。
当前状态：
result = [1, 2, 3, 6, 9, 8, 7, 4]
top = 1, bottom = 1, left = 1, right = 1第五步：从左到右遍历上边界（再次）
接下来遍历上边界，从左到右（当前上边界就是 matrix[1][1]）：
遍历 matrix[1][1] = 5，把它添加到 result 中。
更新 result：[1, 2, 3, 6, 9, 8, 7, 4, 5]
增加 top，使 top = 2。
当前状态：
result = [1, 2, 3, 6, 9, 8, 7, 4, 5]
top = 2, bottom = 1, left = 1, right = 1终止条件
此时 top > bottom，left > right，我们退出循环。
最终结果为：
[1, 2, 3, 6, 9, 8, 7, 4, 5]*/

6. c++ 完整demo：

#include <vector>
#include <iostream>
using namespace std;class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> result;if (matrix.empty()) return result;int top = 0, bottom = matrix.size() - 1;int left = 0, right = matrix[0].size() - 1;while (top <= bottom && left <= right) {// 从左到右沿着最上面一行遍历for (int i = left; i <= right; ++i) {result.push_back(matrix[top][i]);}top++;  // 将顶部边界向下移动// 从上到下沿着最右列遍历。for (int i = top; i <= bottom; ++i) {result.push_back(matrix[i][right]);}right--;  //将右边界向左移动if (top <= bottom) {//从右向左沿着底部一行遍历for (int i = right; i >= left; --i) {result.push_back(matrix[bottom][i]);}bottom--;  //将底部边界向上移动}if (left <= right) {//从底向上沿着最左列遍历for (int i = bottom; i >= top; --i) {result.push_back(matrix[i][left]);}left++;  //将左边界向右移动}}return result;}
};int main() {Solution solution;vector<vector<int>> matrix = {{ 1, 2, 3 },{ 4, 5, 6 },{ 7, 8, 9 }};vector<int> result = solution.spiralOrder(matrix);// 输出结果for (int num : result) {cout << num << " ";}cout << endl;return 0;
}