54.-螺旋矩阵C

JAY.LIN 收录于 Leetcode

2025-03-11 约 1451 字预计阅读 3 分钟

https://bing.ee123.net/img/rand?artid=146188510

54. 螺旋矩阵（C++）

题目

给你一个 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

题解

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

        int rows = matrix.size();
        int cols = matrix[0].size();
        int left = 0, right = cols - 1, top = 0, bottom = rows - 1;

        while (left <= right && top <= bottom) {
            // 从左到右遍历上边界
            for (int col = left; col <= right; col++) {
                result.push_back(matrix[top][col]);
            }
            top++;

            // 从上到下遍历右边界
            for (int row = top; row <= bottom; row++) {
                result.push_back(matrix[row][right]);
            }
            right--;

            // 若上下边界未重合，从右到左遍历下边界
            if (top <= bottom) {
                for (int col = right; col >= left; col--) {
                    result.push_back(matrix[bottom][col]);
                }
                bottom--;
            }

            // 若左右边界未重合，从下到上遍历左边界
            if (left <= right) {
                for (int row = bottom; row >= top; row--) {
                    result.push_back(matrix[row][left]);
                }
                left++;
            }
        }

        return result;
    }
};

算法原理

整体目标

该算法的目标是按照顺时针螺旋顺序遍历一个二维矩阵，并将遍历到的元素依次存储在一个一维向量中返回。为了实现这个目标，我们采用了一种边界控制的方法，通过定义矩阵的四个边界（左、右、上、下），并按照顺时针方向依次遍历这些边界上的元素，同时不断收缩边界，直到遍历完整个矩阵。

1. 初始化边界

在开始遍历之前，我们需要明确矩阵的边界信息。假设矩阵有 m 行 n 列，我们定义四个变量来表示矩阵的边界：

left ：矩阵左边界的列索引，初始值为 0。
right ：矩阵右边界的列索引，初始值为 n - 1 。
top ：矩阵上边界的行索引，初始值为 0。
bottom ：矩阵下边界的行索引，初始值为 m - 1 。

这些边界变量将帮助我们确定每次遍历的范围。

2. 循环遍历矩阵

使用一个 while 循环来控制遍历过程，循环条件为 left <= right 且 top <= bottom 。只要满足这个条件，就说明矩阵中还有未遍历的元素，继续进行遍历。

3. 顺时针遍历边界

在每次循环中，按照顺时针方向依次遍历矩阵的四个边界：

（1）从左到右遍历上边界

for (int col = left; col <= right; col++) {
    result.push_back(matrix[top][col]);
}
top++;

原理：从矩阵的左上角开始，沿着当前上边界（第 top 行）从左到右依次访问元素，并将其添加到结果向量 result 中。遍历完上边界后，上边界向下移动一行，即 top 加 1。

（2）从上到下遍历右边界

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

原理：从当前上边界的下一行（ top 行）开始，沿着右边界（第 right 列）从上到下依次访问元素，并将其添加到结果向量中。遍历完右边界后，右边界向左移动一列，即 right 减 1。

（3）从右到左遍历下边界

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

原理：在遍历下边界之前，需要先检查 top 是否小于等于 bottom ，因为在某些情况下（例如矩阵只有一行），上边界和下边界可能已经重合，此时不需要再遍历下边界。如果满足条件，从当前右边界的左一列（ right 列）开始，沿着下边界（第 bottom 行）从右到左依次访问元素，并将其添加到结果向量中。遍历完下边界后，下边界向上移动一行，即 bottom 减 1。

（4）从下到上遍历左边界

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

原理：在遍历左边界之前，需要先检查 left 是否小于等于 right ，因为在某些情况下（例如矩阵只有一列），左边界和右边界可能已经重合，此时不需要再遍历左边界。如果满足条件，从当前下边界的上一行（ bottom 行）开始，沿着左边界（第 left 列）从下到上依次访问元素，并将其添加到结果向量中。遍历完左边界后，左边界向右移动一列，即 left 加 1。

4. 结束条件

当 left > right 或 top > bottom 时，说明矩阵中的所有元素都已经被遍历完，此时退出循环，返回结果向量 result 。

复杂度分析

时间复杂度 ：由于我们需要遍历矩阵中的每个元素一次，矩阵共有 m * n 个元素，因此时间复杂度为
O ( m ∗ n ) O(m * n)
O
(
m
∗
n
) 。
空间复杂度 ：除了结果向量外，只使用了常数级的额外空间（四个边界变量），因此空间复杂度为
O ( 1 ) O(1)
O
(
1
) 。