当前位置：首页 > news >正文

小哆啦解题记：螺旋矩阵

news 2025/8/26 22:55:21

小哆啦开始刷力扣的第二十八天

54. 螺旋矩阵 - 力扣（LeetCode）

🌪️ 一场螺旋风暴的较量

在一个阳光明媚的午后，小哆啦悠闲地坐在窗边啃着曲奇，突然，一道神秘的光芒闪过，小智从代码的虚空中出现。

“哆啦，我今天带来了一个特别有意思的题目！”小智眨着眼睛说。

“哦？是什么？”小哆啦眯起眼睛，嘴角还沾着饼干屑。

“螺旋矩阵！ ”小智一挥手，白板上赫然出现了一道经典题目：

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

示例：

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

“这也太简单了吧！”小哆啦信心满满地说，“让我来个暴力解法！沿着顺时针走一圈不就好了嘛！”

🚀 第一回合：暴力解法上线

小哆啦撸起袖子，啪啪敲起键盘，写下了第一个版本：

function spiralOrder(matrix: number[][]): number[] {if (matrix.length === 0 || matrix[0].length === 0) return [];const m = matrix.length;const n = matrix[0].length;const result: number[] = [];const visited: boolean[][] = Array.from({ length: m }, () => Array(n).fill(false));let direction = 0; // 0: 右, 1: 下, 2: 左, 3: 上let row = 0, col = 0;const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];for (let i = 0; i < m * n; i++) {result.push(matrix[row][col]);visited[row][col] = true;const nextRow = row + directions[direction][0];const nextCol = col + directions[direction][1];if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && !visited[nextRow][nextCol]) {row = nextRow;col = nextCol;} else {direction = (direction + 1) % 4;row += directions[direction][0];col += directions[direction][1];}}return result;
}

小哆啦按下运行键，屏幕上果然输出了**[1,2,3,6,9,8,7,4,5]**，结果完全正确！

时间复杂度： O(m * n)
空间复杂度： O(m * n)（额外的 visited 数组）

“哈哈哈，我是不是很厉害！”小哆啦得意地转头看向小智。

🌟 小智的灵魂拷问

小智推了推眼镜，嘴角勾起一抹淡淡的微笑：“哆啦，你确定这就是最优解吗？”

小哆啦一愣：“怎么不是？每个元素都访问了一遍，没多走一步啊！”

小智轻敲白板：“可是……你额外用了一个 visited 数组，空间复杂度已经飙到 O(m * n) 了，这不等于背着一大堆行李去爬山吗？”

小哆啦嘴角抽了抽：“那……那怎么改？”

⚡ 第二回合：边界收缩法登场

“我们可以巧妙利用边界收缩法，”小智耐心地解释道，“动态调整上下左右的边界来控制遍历路径，而不是额外用空间去标记访问过的格子。”

小哆啦听完恍然大悟：“等于说，我们把访问过的路径‘挤压’成边界，把矩阵变成一个收缩的战场！”

于是，在小智的引导下，小哆啦写出了第二版代码：

function spiralOrderOptimized(matrix: number[][]): number[] {if (matrix.length === 0 || matrix[0].length === 0) return [];let top = 0, bottom = matrix.length - 1;let left = 0, right = matrix[0].length - 1;const result: number[] = [];while (top <= bottom && left <= right) {for (let i = left; i <= right; i++) result.push(matrix[top][i]); // 从左到右top++;for (let i = top; i <= bottom; i++) result.push(matrix[i][right]); // 从上到下right--;if (top <= bottom) { // 防止重复遍历for (let i = right; i >= left; i--) result.push(matrix[bottom][i]); // 从右到左bottom--;}if (left <= right) { // 防止重复遍历for (let i = bottom; i >= top; i--) result.push(matrix[i][left]); // 从下到上left++;}}return result;
}

时间复杂度： O(m * n)
空间复杂度： O(1)