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;
}