跳到主要内容

LeetCode 54. 螺旋矩阵

本节目标

用四条边界表示尚未访问的矩形，按层完成顺时针遍历。

这道题是矩阵解题框架的边界收缩母题。代码看似只是四段循环，真正需要维护的是“尚未访问区域”的精确定义。

查看原题

题意与约束​

给定一个 m × n 矩阵，按照从左到右、从上到下、从右到左、从下到上的顺时针顺序，返回所有元素。

矩阵可能只有一行或一列，因此最后一层未必仍有完整的四条边。

第一反应：记录访问状态​

可以从左上角出发，遇到边界或已访问位置就转向，并用额外矩阵标记访问状态。这个方法能做，但状态较多，也没有利用螺旋顺序天然按矩形外圈推进的结构。

四条边界​

令 top、bottom、left、right 包围尚未访问的矩形。每轮依次：

  1. 遍历上边，然后 top 下移；
  2. 遍历右边，然后 right 左移；
  3. 若仍有剩余行，遍历下边，然后 bottom 上移；
  4. 若仍有剩余列，遍历左边，然后 left 右移。

循环不变量是：进入每轮时，边界内的矩形恰好由所有未访问元素组成。

后两条边必须先检查边界。如果最后只剩一行，直接遍历下边会重复；只剩一列时同理。

代码实现​

两份实现都只维护四个整数边界，不使用访问标记。

C++17
#include <vector>
using namespace std;

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

        int top = 0;
        int bottom = static_cast<int>(matrix.size()) - 1;
        int left = 0;
        int right = static_cast<int>(matrix[0].size()) - 1;

        while (top <= bottom && left <= right) {
            for (int col = left; col <= right; col++) {
                order.push_back(matrix[top][col]);
            }
            top++;

            for (int row = top; row <= bottom; row++) {
                order.push_back(matrix[row][right]);
            }
            right--;

            if (top <= bottom) {
                for (int col = right; col >= left; col--) {
                    order.push_back(matrix[bottom][col]);
                }
                bottom--;
            }

            if (left <= right) {
                for (int row = bottom; row >= top; row--) {
                    order.push_back(matrix[row][left]);
                }
                left++;
            }
        }

        return order;
    }
};

复杂度分析​

  • 时间复杂度：O(mn)，每个元素恰好加入答案一次。
  • 空间复杂度：O(1)，不计返回数组，只使用四个边界变量。

易错点​

  • 遍历下边和左边前不检查剩余边界，重复访问单行或单列。
  • 更新边界的时机错误，把刚访问过的边仍视为未处理区域。
  • 用固定四段循环处理空矩阵，提前访问 matrix[0]。
  • 把坐标的行列含义写反，长方形矩阵才暴露错误。

模式迁移​

边界收缩还适用于按层打印、矩阵分圈旋转和生成螺旋矩阵。迁移时不必记忆转向细节，只要持续维护“边界内恰好是未处理区域”，再按题目要求决定每轮访问哪几条边。