HHot 100C++ 图解

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]

 

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

思路

时间O(mn)
空间O(1)(不算输出)

思路

四边界收缩。右->下->左->上 各走一遍,每遍结束后收缩对应边界,并且「左/上」两遍走之前要再判一次区间是否还有效(只剩一行/一列时会重复走)。

图解

j0 j1 j2 j3 i0 1 2 3 4 i1 5 6 7 8 i2 9 10 11 12
矩阵(来自本仓库测试数据,红色格子 = 0)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/06_matrix.cpp26 行
namespace lc0054 {
class Solution {
 public:
  vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> ans;
    if (matrix.empty() || matrix[0].empty()) return ans;  // 不然下面的 matrix[0].size() 就是越界
    int top = 0, bottom = (int)matrix.size() - 1;
    int left = 0, right = (int)matrix[0].size() - 1;
    while (top <= bottom && left <= right) {
      for (int j = left; j <= right; ++j) ans.push_back(matrix[top][j]);  // →
      ++top;
      for (int i = top; i <= bottom; ++i) ans.push_back(matrix[i][right]);  // ↓
      --right;
      if (top <= bottom) {  // 关键判空:只剩一行时不能再往回走
        for (int j = right; j >= left; --j) ans.push_back(matrix[bottom][j]);  // ←
        --bottom;
      }
      if (left <= right) {  // 只剩一列时同理
        for (int i = bottom; i >= top; --i) ans.push_back(matrix[i][left]);  // ↑
        ++left;
      }
    }
    return ans;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q54_spiral_matrix13 行
lc0054::Solution s;
vector<vector<int>> a{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
CHECK_EQ(s.spiralOrder(a), vector<int>{1, 2, 3, 6, 9, 8, 7, 4, 5});
vector<vector<int>> b{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
CHECK_EQ(s.spiralOrder(b), vector<int>{1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7});
vector<vector<int>> c{{1, 2}, {3, 4}, {5, 6}};  // 竖长
CHECK_EQ(s.spiralOrder(c), vector<int>{1, 2, 4, 6, 5, 3});
vector<vector<int>> d{{1, 2, 3}};  // 单行:走到「←」时靠 `top <= bottom` 跳过
CHECK_EQ(s.spiralOrder(d), vector<int>{1, 2, 3});
vector<vector<int>> e{{1}, {2}, {3}};  // 单列:靠 `left <= right` 跳过重复的「↑」
CHECK_EQ(s.spiralOrder(e), vector<int>{1, 2, 3});
vector<vector<int>> f{};  // 空输入
CHECK_EQ(s.spiralOrder(f), vector<int>{});

↑↓ 选择↵ 打开/ 随时唤起