LeetCode 885(Spiral Matrix III)超时问题排查与时间复杂度咨询

一、超时原因直白解释 #

超时就是你的代码运行速度太慢，LeetCode对每个题目的运行时间有上限（比如1秒），如果你的代码在处理大测试用例时，做了太多没必要的循环或者操作，就会超过这个时间限制，触发超时错误。

二、常见超时问题排查与优化方向 #

针对Spiral Matrix III这个题，最容易导致超时的问题就是做了无意义的遍历：比如明明已经收集完所有需要的网格坐标，还继续沿着螺旋路径走下去，或者遍历范围远大于实际需要的区域。

三、具体代码优化示例 #

假设你的代码存在上述问题，以下是具体的优化点：

错误代码示例（常见超时写法） #

public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
    List<int[]> res = new ArrayList<>();
    int x = rStart, y = cStart;
    int step = 1;
    int dir = 0; // 0:右, 1:下, 2:左, 3:上
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    
    // 无限循环，直到覆盖所有可能区域，没及时终止
    while (true) {
        for (int i = 0; i < step; i++) {
            if (x >= 0 && x < rows && y >=0 && y < cols) {
                res.add(new int[]{x, y});
            }
            x += dirs[dir][0];
            y += dirs[dir][1];
        }
        dir = (dir + 1) % 4;
        if (dir % 2 == 0) {
            step++;
        }
    }
}

优化后的代码 #

public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
    int total = rows * cols;
    List<int[]> res = new ArrayList<>();
    int x = rStart, y = cStart;
    int step = 1;
    int dir = 0; // 0:右, 1:下, 2:左, 3:上
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    
    // 只遍历到收集完所有元素为止
    while (res.size() < total) {
        for (int i = 0; i < step; i++) {
            if (x >= 0 && x < rows && y >=0 && y < cols) {
                res.add(new int[]{x, y});
                // 收集完立刻返回，不用继续遍历
                if (res.size() == total) {
                    return res.toArray(new int[total][]);
                }
            }
            x += dirs[dir][0];
            y += dirs[dir][1];
        }
        dir = (dir + 1) % 4;
        if (dir % 2 == 0) {
            step++;
        }
    }
    return res.toArray(new int[total][]);
}

关键优化代码行说明 #

1. 循环条件修改：把无限while(true)改成while(res.size() < total)，避免无意义的循环。
2. 提前终止判断：在每次添加元素到结果列表后，检查res.size() == total，如果满足就直接返回结果，不用继续走完当前步数或切换方向。

这两处优化能大幅减少不必要的遍历次数，直接解决超时问题。

内容的提问来源于stack exchange，提问作者Puneet Chhabra