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.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
思路
时间
O(mn)空间
O(1)(不算输出)思路
四边界收缩。右->下->左->上 各走一遍,每遍结束后收缩对应边界,并且「左/上」两遍走之前要再判一次区间是否还有效(只剩一行/一列时会重复走)。
图解
矩阵(来自本仓库测试数据,红色格子 = 0)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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>{});