LeetCode 题解工作台
螺旋矩阵 III
在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。 你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。 …
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
class Solution: def spiralMatrixIII(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。
最终，我们到过网格的所有 rows x cols 个空间。
按照访问顺序返回表示网格位置的坐标列表。
示例 1：
输入：rows = 1, cols = 4, rStart = 0, cStart = 0 输出：[[0,0],[0,1],[0,2],[0,3]]
示例 2：
输入：rows = 5, cols = 6, rStart = 1, cStart = 4 输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
提示：
1 <= rows, cols <= 1000 <= rStart < rows0 <= cStart < cols
解题思路
方法一
class Solution:
def spiralMatrixIII(
self, rows: int, cols: int, rStart: int, cStart: int
) -> List[List[int]]:
ans = [[rStart, cStart]]
if rows * cols == 1:
return ans
k = 1
while True:
for dr, dc, dk in [[0, 1, k], [1, 0, k], [0, -1, k + 1], [-1, 0, k + 1]]:
for _ in range(dk):
rStart += dr
cStart += dc
if 0 <= rStart < rows and 0 <= cStart < cols:
ans.append([rStart, cStart])
if len(ans) == rows * cols:
return ans
k += 2
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(\max(\text{rows}, \text{cols})^2) |
| 空间 | O(\text{rows} \cdot \text{cols}) |
面试官常问的追问
外企场景- question_mark
Ensure the candidate handles grid boundaries properly while maintaining an efficient traversal.
- question_mark
Look for the ability to simulate the process step-by-step and adapt to boundary conditions.
- question_mark
Evaluate the candidate's approach to optimizing the space complexity when working with large grids.
常见陷阱
外企场景- error
Failing to handle the grid boundaries properly, leading to unnecessary moves or invalid coordinates.
- error
Not correctly simulating the clockwise spiral movement, leading to incorrect ordering of visited coordinates.
- error
Mismanaging the direction changes, which might cause infinite loops or missing cells.
进阶变体
外企场景- arrow_right_alt
Handling different grid sizes, including very narrow grids (e.g., 1xN or Nx1).
- arrow_right_alt
Optimizing the solution to avoid unnecessary memory usage for very large grids.
- arrow_right_alt
Considering cases where the starting point is at the edge or corner of the grid.