leetcode：54. 螺旋矩阵

题目

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

解答 & 代码

沿上、右、下、左四个边界走，没走完一个边界，对应边界收缩

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return {};
        int rows = matrix.size();
        int cols = matrix[0].size();

        int up = 0;                // 上边界
        int down = rows - 1;    // 下边界
        int left = 0;            // 左边界
        int right = cols - 1;    // 右边界
        vector<int> result;
        // 遍历二维矩阵的每个位置
        while(result.size() < rows * cols)
        {
            if(up <= down)
            {
                // 从左往右遍历上边界
                for(int j = left; j <= right; ++j)
                    result.push_back(matrix[up][j]);
                ++up;        // 上边界收缩（下移）
            }

            if(right >= left)
            {
                // 从上往下遍历右边界
                for(int i = up; i <= down; ++i)
                    result.push_back(matrix[i][right]);
                --right;    // 右边界收缩（左移
            }

            if(down >= up)
            {
                // 从右往左遍历下边界
                for(int j = right; j >= left; --j)
                    result.push_back(matrix[down][j]);
                --down;        // 下边界收缩（上移）
            }

            if(left <= right)
            {
                // 从下往上遍历左边界
                for(int i = down; i >= up; --i)
                    result.push_back(matrix[i][left]);
                ++left;        // 左边界收缩（右移）
            }
        }
        return result;
    }
};

复杂度分析：矩阵 matrix m 行 n 列

• 时间复杂度 O(mn)：遍历每个位置
• 空间复杂度 O(1)：结果数组空间复杂度不计

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6.6 MB, 在所有 C++ 提交中击败了 69.28% 的用户