Medium

题目描述

在 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 <= 100
  • 0 <= rStart < rows
  • 0 <= cStart < cols

解题思路

解题思路

这道题需要模拟螺旋行走的过程。关键观察是螺旋的行走模式：

  • 方向循环：东 → 南 → 西 → 北
  • 步数规律：1步(东) → 1步(南) → 2步(西) → 2步(北) → 3步(东) → 3步(南) → 4步(西) → 4步(北)…

具体规律是：

  1. 每两个方向为一组，步数相同
  2. 每组的步数比前一组多1

算法步骤：

  1. 定义四个方向向量：东、南、西、北
  2. 从起始位置开始，按照螺旋规律行走
  3. 每次移动时检查当前位置是否在网格内，如果在则记录
  4. 继续行走直到访问完所有网格位置

优化点：

  • 可以预先计算总步数，避免无限循环
  • 使用方向数组简化代码逻辑

时间复杂度主要取决于需要走多少步才能覆盖所有网格位置，最坏情况下需要走到边界很远的地方。

代码实现

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> result;
        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 东南西北
        
        int r = rStart, c = cStart;
        int dirIdx = 0; // 当前方向索引
        int steps = 1; // 当前步数
        
        result.push_back({r, c}); // 添加起始位置
        
        while (result.size() < rows * cols) {
            for (int i = 0; i < 2; i++) { // 每两个方向步数相同
                for (int j = 0; j < steps; j++) {
                    r += directions[dirIdx][0];
                    c += directions[dirIdx][1];
                    
                    if (r >= 0 && r < rows && c >= 0 && c < cols) {
                        result.push_back({r, c});
                    }
                }
                dirIdx = (dirIdx + 1) % 4; // 转向下一个方向
            }
            steps++; // 每完成两个方向，步数增加
        }
        
        return result;
    }
};

class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
        result = []
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 东南西北
        
        r, c = rStart, cStart
        dir_idx = 0  # 当前方向索引
        steps = 1  # 当前步数
        
        result.append([r, c])  # 添加起始位置
        
        while len(result) < rows * cols:
            for _ in range(2):  # 每两个方向步数相同
                for _ in range(steps):
                    r += directions[dir_idx][0]
                    c += directions[dir_idx][1]
                    
                    if 0 <= r < rows and 0 <= c < cols:
                        result.append([r, c])
                
                dir_idx = (dir_idx + 1) % 4  # 转向下一个方向
            steps += 1  # 每完成两个方向，步数增加
        
        return result

public class Solution {
    public int[][] SpiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        var result = new List<int[]>();
        int[,] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 东南西北
        
        int r = rStart, c = cStart;
        int dirIdx = 0; // 当前方向索引
        int steps = 1; // 当前步数
        
        result.Add(new int[] {r, c}); // 添加起始位置
        
        while (result.Count < rows * cols) {
            for (int i = 0; i < 2; i++) { // 每两个方向步数相同
                for (int j = 0; j < steps; j++) {
                    r += directions[dirIdx, 0];
                    c += directions[dirIdx, 1];
                    
                    if (r >= 0 && r < rows && c >= 0 && c < cols) {
                        result.Add(new int[] {r, c});
                    }
                }
                dirIdx = (dirIdx + 1) % 4; // 转向下一个方向
            }
            steps++; // 每完成两个方向，步数增加
        }
        
        return result.ToArray();
    }
}

var spiralMatrixIII = function(rows, cols, rStart, cStart) {
    const result = [];
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // 东南西北
    
    let r = rStart, c = cStart;
    let dirIdx = 0; // 当前方向索引
    let steps = 1; // 当前步数
    
    result.push([r, c]); // 添加起始位置
    
    while (result.length < rows * cols) {
        for (let i = 0; i < 2; i++) { // 每两个方向步数相同
            for (let j = 0; j < steps; j++) {
                r += directions[dirIdx][0];
                c += directions[dirIdx][1];
                
                if (r >= 0 && r < rows && c >= 0 && c < cols) {
                    result.push([r, c]);
                }
            }
            dirIdx = (dirIdx + 1) % 4; // 转向下一个方向
        }
        steps++; // 每完成两个方向，步数增加
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O((max(rows, cols))²)最坏情况下需要走到距离网格较远的地方才能覆盖所有位置
空间复杂度O(1)除了结果数组外，只使用常数额外空间

相关题目