leetcode 链接：螺旋矩阵

题目

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

解答 & 代码

解法一

建立一个和 matrix 一样的的矩阵来存储每个元素是否被访问过
因此，如果 matrix 矩阵为 M 行 N 列，则时间复杂度 O(MN)，空间复杂度 O(MN)

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));    // 存储矩阵中每个元素是否被访问过

        vector<int> result;
        int row = 0, col = 0;
        while(row >= 0 && row < rows && col >= 0 && col < cols && !visited[row][col])
        {
            while(col < cols && !visited[row][col])        // 向右走
            {
                result.push_back(matrix[row][col]);
                visited[row][col] = true;
                ++col;
            }

            ++row;
            --col;
            while(row < rows && !visited[row][col])        // 向下走
            {
                result.push_back(matrix[row][col]);
                visited[row][col] = true;
                ++row;
            }

            --row;
            --col;
            while(col >= 0 && !visited[row][col])        // 向左走
            {
                result.push_back(matrix[row][col]);
                visited[row][col] = true;
                --col;
            }

            --row;
            ++col;
            while(row >= 0 && !visited[row][col])        // 向上走
            {
                result.push_back(matrix[row][col]);
                visited[row][col] = true;
                --row;
            }

            ++row;
            ++col;
        }

        return result;
    }
};

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 34.35% 的用户
内存消耗：6.8 MB, 在所有 C++ 提交中击败了 9.34% 的用户

解法二

不使用额外的矩阵来记录元素是否被访问过，而是通过收缩四周边界值的方式来限定遍历范围
因此，如果 matrix 矩阵为 M 行 N 列，则时间复杂度 O(MN)，空间复杂度 O(1)

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;                // 存储结果
        int rows = matrix.size();        // 行数
        if(rows == 0)
            return result;
        int cols = matrix[0].size();    // 列数
        if(cols == 0)
            return result;

        // 左、右、上、下边界
        int left = 0, right = cols - 1, up = 0, down = rows - 1;
        while(left <= right && up <= down)
        {
            // 访问上边界这一行，向右移动直到移动到右边界
            for(int col = left; col <= right; ++col)    
                result.push_back(matrix[up][col]);
            ++up;                // 上边界下移一格
            if(up > down)        // 如果上边界大于下边界，则遍历结束
                break;            
            // 访问右边界这一列，向下移动直到移动到下边界
            for(int row = up; row <= down; ++row)
                result.push_back(matrix[row][right]);
            --right;            // 右边界左移一格
            if(right < left)    // 如果右边界小于左边界，则遍历结束
                break;
            // 访问下边界这一行，向左移动直到移动到左边界
            for(int col = right; col >= left; --col)
                result.push_back(matrix[down][col]);
            --down;                // 下边界上移一格
            if(down < up)        // 如果下边界小于上边界，则遍历结束
                break;
            // 访问左边界这一列，向上移动直到移动到上边界
            for(int row = down; row >= up; --row)
                result.push_back(matrix[row][left]);
            ++left;                // 左边界右移一格
            if(left > right)    // 如果左边界大于右边界，则遍历结束
                break;
        }

        return result;
    }
};