54. 螺旋矩阵
题目描述
输入一个 m 行 n 列的矩阵 matrix。
从左上角出发，沿顺时针方向一圈一圈向内绕：先向右走完第一行，再向下、向左、向上，依此类推，直到每个元素都被访问一次。
按访问的先后顺序，把所有元素放进一个数组返回。
示例 1
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
解释：外圈依次是 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]
解释：外圈走完 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)（不计输出）。
易错点
单行或单列剩余时要检查边界，避免重复遍历。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def spiralOrder(self, matrix):
ans=[]; top,bottom=0,len(matrix)-1; left,right=0,len(matrix[0])-1
while top<=bottom and left<=right:
for j in range(left,right+1): ans.append(matrix[top][j])
top+=1
for i in range(top,bottom+1): ans.append(matrix[i][right])
right-=1
if top<=bottom:
for j in range(right,left-1,-1): ans.append(matrix[bottom][j])
bottom-=1
if left<=right:
for i in range(bottom,top-1,-1): ans.append(matrix[i][left])
left+=1
return ansclass Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>(); int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) ans.add(matrix[top][j]);
top++;
for (int i = top; i <= bottom; i++) ans.add(matrix[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) ans.add(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) ans.add(matrix[i][left]);
left++;
}
}
return ans;
}
}class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans; int top = 0, bottom = matrix.size() - 1, left = 0, right = 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;
}
};func spiralOrder(matrix [][]int) []int {
ans := []int{}; top, bottom := 0, len(matrix)-1; left, right := 0, len(matrix[0])-1
for top <= bottom && left <= right {
for j := left; j <= right; j++ {
ans = append(ans, matrix[top][j])
}
top++
for i := top; i <= bottom; i++ {
ans = append(ans, matrix[i][right])
}
right--
if top <= bottom {
for j := right; j >= left; j-- {
ans = append(ans, matrix[bottom][j])
}
bottom--
}
if left <= right {
for i := bottom; i >= top; i-- {
ans = append(ans, matrix[i][left])
}
left++
}
}
return ans
}var spiralOrder = function(matrix) {
const ans = []; let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (let j = left; j <= right; j++) ans.push(matrix[top][j]);
top++;
for (let i = top; i <= bottom; i++) ans.push(matrix[i][right]);
right--;
if (top <= bottom) {
for (let j = right; j >= left; j--) ans.push(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (let i = bottom; i >= top; i--) ans.push(matrix[i][left]);
left++;
}
}
return ans;
};function spiralOrder(matrix: number[][]): number[] {
const ans: number[] = []; let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (let j = left; j <= right; j++) ans.push(matrix[top][j]);
top++;
for (let i = top; i <= bottom; i++) ans.push(matrix[i][right]);
right--;
if (top <= bottom) {
for (let j = right; j >= left; j--) ans.push(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (let i = bottom; i >= top; i--) ans.push(matrix[i][left]);
left++;
}
}
return ans;
}其他解法
按层收缩边界只用常数空间，但要仔细处理单行、单列的情况；方向模拟更好写，需要额外标记空间。
解法 2：方向模拟 + 访问标记 时间 O(m·n)，空间 O(m·n)
从左上角出发，按右、下、左、上的顺序循环使用方向。用同样大小的布尔矩阵记录已访问的格子。下一步越界或已访问时，顺时针转向。一共走 m·n 步。
不需要处理四条边界的细节，逻辑直观，不易出错。代价是额外的 O(m·n) 标记矩阵。
class Solution:
def spiralOrder(self, matrix):
m, n = len(matrix), len(matrix[0])
seen = [[False] * n for _ in range(m)]
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
ans = []
i = j = d = 0
for _ in range(m * n):
ans.append(matrix[i][j])
seen[i][j] = True
ni, nj = i + dirs[d][0], j + dirs[d][1]
if not (0 <= ni < m and 0 <= nj < n and not seen[ni][nj]):
d = (d + 1) % 4
ni, nj = i + dirs[d][0], j + dirs[d][1]
i, j = ni, nj
return ansclass Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[][] seen = new boolean[m][n];
int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0};
List<Integer> ans = new ArrayList<>();
int i = 0, j = 0, d = 0;
for (int k = 0; k < m * n; k++) {
ans.add(matrix[i][j]);
seen[i][j] = true;
int ni = i + dr[d], nj = j + dc[d];
if (ni < 0 || ni >= m || nj < 0 || nj >= n || seen[ni][nj]) {
d = (d + 1) % 4;
ni = i + dr[d];
nj = j + dc[d];
}
i = ni;
j = nj;
}
return ans;
}
}class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<bool>> seen(m, vector<bool>(n, false));
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
vector<int> ans;
int i = 0, j = 0, d = 0;
for (int k = 0; k < m * n; k++) {
ans.push_back(matrix[i][j]);
seen[i][j] = true;
int ni = i + dr[d], nj = j + dc[d];
if (ni < 0 || ni >= m || nj < 0 || nj >= n || seen[ni][nj]) {
d = (d + 1) % 4;
ni = i + dr[d];
nj = j + dc[d];
}
i = ni;
j = nj;
}
return ans;
}
};func spiralOrder(matrix [][]int) []int {
m, n := len(matrix), len(matrix[0])
seen := make([][]bool, m)
for r := range seen {
seen[r] = make([]bool, n)
}
dr, dc := []int{0, 1, 0, -1}, []int{1, 0, -1, 0}
ans := []int{}
i, j, d := 0, 0, 0
for k := 0; k < m*n; k++ {
ans = append(ans, matrix[i][j])
seen[i][j] = true
ni, nj := i+dr[d], j+dc[d]
if ni < 0 || ni >= m || nj < 0 || nj >= n || seen[ni][nj] {
d = (d + 1) % 4
ni, nj = i+dr[d], j+dc[d]
}
i, j = ni, nj
}
return ans
}var spiralOrder = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const seen = Array.from({ length: m }, () => Array(n).fill(false));
const dr = [0, 1, 0, -1], dc = [1, 0, -1, 0];
const ans = [];
let i = 0, j = 0, d = 0;
for (let k = 0; k < m * n; k++) {
ans.push(matrix[i][j]);
seen[i][j] = true;
let ni = i + dr[d], nj = j + dc[d];
if (ni < 0 || ni >= m || nj < 0 || nj >= n || seen[ni][nj]) {
d = (d + 1) % 4;
ni = i + dr[d];
nj = j + dc[d];
}
i = ni;
j = nj;
}
return ans;
};function spiralOrder(matrix: number[][]): number[] {
const m = matrix.length, n = matrix[0].length;
const seen: boolean[][] = Array.from({ length: m }, () => Array(n).fill(false));
const dr = [0, 1, 0, -1], dc = [1, 0, -1, 0];
const ans: number[] = [];
let i = 0, j = 0, d = 0;
for (let k = 0; k < m * n; k++) {
ans.push(matrix[i][j]);
seen[i][j] = true;
let ni = i + dr[d], nj = j + dc[d];
if (ni < 0 || ni >= m || nj < 0 || nj >= n || seen[ni][nj]) {
d = (d + 1) % 4;
ni = i + dr[d];
nj = j + dc[d];
}
i = ni;
j = nj;
}
return ans;
}