跳转至

54 螺旋矩阵

和螺旋矩阵II n行n列 不同,螺旋矩阵这道题是m行n列,这意味着:

  • 我们如果按螺旋矩阵左闭右开区间不一定能遍历完所有元素,例如对于1行2列[1,2],按螺旋矩阵II的做法只能遍历元素1 -> 采用左闭右闭区间
  • 我们需要定义四个变量:起始行和终止行,起始列和终止列
  • 并且我们无法确定遍历的次数,因为行列长度不同 -> 采用while(true)

本题思路大致如下图:

fig1

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

        vector<int> ans;
        int startCol = 0, endCol = matrix[0].size() - 1; // 记录行的开头与结尾
        int startRow = 0, endRow = matrix.size() - 1; // 记录列的开头与结尾

        while(true)
        {
            // 从左往右
            for(int i = startCol; i <= endCol; i++)
                ans.push_back(matrix[startRow][i]);
            if(++startRow > endRow) break;

            // 从上往下
            for(int i = startRow; i <= endRow; i++)
                ans.push_back(matrix[i][endCol]);
            if(--endCol < startCol) break;

            // 从右往左
            for(int i = endCol; i >= startCol; i--)
                ans.push_back(matrix[endRow][i]);
            if(--endRow < startRow) break;

            // 从下往上
            for(int i = endRow; i >= startRow; i--)
                ans.push_back(matrix[i][startCol]);
            if(++startCol > endCol) break;
        }
        return ans;
    }
};

时间复杂度:O(mn),其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

空间复杂度:O(1)。除了输出数组以外,空间复杂度是常数。