LeetCode 874. 模拟行走机器人

2026-03-07 HGNULB 约 9 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 874. 模拟行走机器人

题意分析

机器人站在原点，面朝北方，指令流里混着三种东西：-2 表示原地左转 90 度，-1 表示原地右转 90 度，1 到 9 之间的正数表示沿当前朝向前进若干格。

要返回的不是终点到原点的距离，而是「整个行走过程中曾经到达过的最远点」的欧氏距离平方。这两个词都是信号：一是答案要在过程中持续更新，不能等走完再算；二是返回平方值，省掉开方，全程只用整数。

障碍的语义要读准：机器人是一格一格挪的，撞上障碍格时它停在障碍前面那一格，这条前进指令剩下的步数直接作废，但朝向不受影响，下一条指令照常执行。障碍格本身永远进不去。

约束给了两个规模信号：指令最多 $10^4$ 条，每条最多前进 9 格，所以总步数量级是 $10^5$；障碍最多 $10^4$ 个，坐标绝对值不超过 $3 \times 10^4$。这意味着「逐格走」是可以接受的，但「每格都把障碍表扫一遍」不行。

边界上要留意：障碍可能压根不在路径上，也可能紧贴起点；坐标会出现负数；指令可能全是转向，此时答案就是起点的 $0$。

解法：哈希集合 + 模拟

核心思路

最朴素的做法是照着题意演：开一个二维网格标记障碍，机器人每挪一格就查一次网格。可坐标范围是 $[-3 \times 10^4, 3 \times 10^4]$，二维数组要开 $6 \times 10^4$ 见方共 $3.6 \times 10^9$ 个格子，内存直接爆掉。

退一步用障碍数组：每挪一格就遍历 $10^4$ 个障碍比对坐标。总步数 $10^5$ 乘以 $10^4$ 是 $10^9$ 次比较，时间又不够。

瓶颈定位得很清楚：稀疏的障碍点被存成了稠密结构，或者被存成了只能顺序查的结构。观察到我们对障碍的全部诉求只有一句「这个坐标是不是障碍」，既不关心顺序，也不关心它属于哪个障碍——那就把二维坐标压成一个可哈希的键塞进集合，把查询降到 $O(1)$。压键的方式必须是单射：把 $x$ 左移 32 位，再把 $y$ 的低 32 位拼上去，得到一个 64 位整数，正负坐标都能唯一还原。

于是整个过程可以用一组不变量描述。设三元组 $(x, y, d)$ 为机器人的完整状态，$d \in {0,1,2,3}$ 依次对应北、东、南、西四个朝向。这个方向顺序是顺时针排列的，因此右转就是 $d \leftarrow (d+1) \bmod 4$，左转就是 $d \leftarrow (d+3) \bmod 4$，不需要写四路分支。另一个不变量是答案变量 $best$：在任意时刻，它恒等于「机器人已经踩过的所有格点中 $x^2 + y^2$ 的最大值」。每成功挪动一格就立刻维护它，这个等式就永远成立。

解题步骤

遍历障碍数组，把每个 (x, y) 压成 64 位键存入哈希集合。为什么先建集合：后面每挪一格都要查一次，必须先把查询代价压到常数。

准备方向表 dirs，按北、东、南、西的顺时针次序排好，初始 dir = 0、x = y = 0、best = 0。为什么按顺时针排：这样左右转都能退化成对下标的模 4 加法。

顺序扫描指令。遇到 -2 执行 dir = (dir + 3) % 4，遇到 -1 执行 dir = (dir + 1) % 4。为什么左转是加 3 不是减 1：在多数语言里负数取模的结果符号跟随被除数，加 3 与减 1 在模 4 意义下等价却不会出现负下标。

遇到正数 cmd 时，做 cmd 次单步尝试：先算出候选格 (nx, ny)，查集合；命中障碍就 break 掉这层内循环，否则把 (x, y) 更新为 (nx, ny) 并用 $x^2+y^2$ 刷新 best。为什么要先算候选再判断：判断的对象必须是「即将进入的格子」，拿当前所在格去判断会让机器人多走一格踩到障碍上。

为什么 break 只跳内循环：题目规定撞墙只作废这条指令剩余的步数，朝向和后续指令都不受影响，跳出外层会漏掉后面的路径。

以 commands = [4, -1, 4, -2, 4]、obstacles = [[2, 4]] 走一遍：集合里只有一个键，对应 $(2, 4)$。初始 $(x,y)=(0,0)$，$d=0$（北），$best=0$。第一条指令 4，沿北方逐格挪到 $(0,1)$、$(0,2)$、$(0,3)$、$(0,4)$，四步都不撞障碍，$best$ 依次变成 $1, 4, 9, 16$。第二条指令 -1 右转，$d=(0+1)\bmod 4=1$，朝东。第三条指令 4，第一步候选 $(1,4)$ 不是障碍，移动过去，$best=\max(16, 1+16)=17$；第二步候选 $(2,4)$ 正好是障碍，break，机器人停在 $(1,4)$，剩下两步作废。第四条指令 -2 左转，$d=(1+3)\bmod 4=0$，重新朝北。第五条指令 4，从 $(1,4)$ 依次到 $(1,5)$、$(1,6)$、$(1,7)$、$(1,8)$，对应的平方距离是 $26, 37, 50, 65$，$best$ 最终被刷成 $65$。返回 $65$。

代码实现

// 维护当前方向，按指令移动或转向。
class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        Set<Long> block = new HashSet<>();
        for (int[] o : obstacles) {
            long key = (((long) o[0]) << 32) ^ (o[1] & 0xffffffffL);
            block.add(key);
        }

        int[][] dirs = new int[4][2];
        dirs[0] = new int[] {0, 1};
        dirs[1] = new int[] {1, 0};
        dirs[2] = new int[] {0, -1};
        dirs[3] = new int[] {-1, 0};
        int dir = 0;
        int x = 0;
        int y = 0;
        int best = 0;

        for (int cmd : commands) {
            if (cmd == -2) {
                dir = (dir + 3) % 4;
            } else if (cmd == -1) {
                dir = (dir + 1) % 4;
            } else {
                for (int i = 0; i < cmd; i++) {
                    int nx = x + dirs[dir][0];
                    int ny = y + dirs[dir][1];
                    long key = (((long) nx) << 32) ^ (ny & 0xffffffffL);
                    if (block.contains(key)) {
                        break;
                    }
                    x = nx;
                    y = ny;
                    best = Math.max(best, x * x + y * y);
                }
            }
        }

        return best;
    }
}

// 维护当前方向，按指令移动或转向。
func robotSim(commands []int, obstacles [][]int) int {
    block := make(map[int64]bool)
    for _, o := range obstacles {
        key := (int64(o[0]) << 32) ^ int64(uint32(o[1]))
        block[key] = true
    }

    dirs := make([][2]int, 0, 4)
    dirs = append(dirs, [2]int{0, 1}, [2]int{1, 0}, [2]int{0, -1}, [2]int{-1, 0})
    dir := 0
    x, y := 0, 0
    best := 0

    for _, cmd := range commands {
        if cmd == -2 {
            dir = (dir + 3) % 4
        } else if cmd == -1 {
            dir = (dir + 1) % 4
        } else {
            for step := 0; step < cmd; step++ {
                nx := x + dirs[dir][0]
                ny := y + dirs[dir][1]
                key := (int64(nx) << 32) ^ int64(uint32(ny))
                if block[key] {
                    break
                }
                x, y = nx, ny
                dist := x*x + y*y
                if dist > best {
                    best = dist
                }
            }
        }
    }

    return best
}

复杂度分析

时间复杂度：$O(m + S)$，其中 $m$ 是障碍数量，$S$ 是所有前进指令的步数之和。建集合扫一遍障碍是 $O(m)$；之后每一格只做一次哈希查询和一次常数更新，转向指令是 $O(1)$。由于每条指令最多前进 9 格，$S \le 9n$，$n$ 为指令条数。

空间复杂度：$O(m)$，哈希集合里存了全部障碍键，方向表和四个标量都是常数级，与指令长度无关。

关键点总结

稀疏点集用哈希集合而不是二维数组，是坐标范围大、点数少时的标准换位思考：内存从坐标跨度决定变成点数决定。

二维坐标压成单值键时，映射必须是单射且能容纳负数。左移 32 位再拼低 32 位是最省心的写法，比字符串拼接快，比线性组合安全。

把方向按顺时针排进数组，转向就退化成模 4 加法，代码里不会出现四个 if 分支，面试白板上少写十几行也少错十几处。

「过程中的最优」和「结束时的结果」是两类题，前者必须在每次状态变化后立刻更新答案，把答案维护写成循环不变量能自证正确性。

面试视角：这题的考点不是模拟本身，而是你能不能一眼看出「$3 \times 10^4$ 的坐标范围 + $10^4$ 个障碍」是在暗示哈希。先说出二维数组会爆内存、线性扫会超时，再给出集合方案，比直接写代码更能拿分。

易错点总结

错误写法：把 -2 当成右转、-1 当成左转。用例 commands = [4, -1, 4, -2, 4] 会让机器人先向西再向南，返回一个远小于 65 的值。

错误写法：撞到障碍后仍按「这条指令走满」的终点坐标去更新答案。用例 commands = [4, -1, 8]、obstacles = [[2, 4]]，真实停点是 $(1,4)$，却会把走不到的 $(8,4)$ 记进答案。

错误写法：撞障碍后 return 或跳出外层指令循环。用例中第三条指令被挡住后还有一次左转和一次前进，提前退出会漏掉最终的 $(1,8)$。

错误写法：障碍存成数组或列表，每挪一格线性遍历一次。在指令与障碍都逼近 $10^4$ 的数据上是 $10^9$ 级比较，直接超时。

错误写法：用 x * 30001 + y 之类的线性组合当哈希键。坐标含负数时不同点会撞到同一个键，程序会把空地误判成障碍，机器人无故停下。

错误写法：判断障碍时用当前所在格 (x, y) 而不是候选格 (nx, ny)。机器人会先踩进障碍格再发现，结果多走一格。

错误写法：转向分支处理完忘记跳过后续的前进逻辑，把 -1 当成步数。循环次数为负会直接不执行或抛异常，取决于写法。

错误写法：返回开方后的欧氏距离。题目要的是平方值，开方既丢精度又改变了返回类型。

错误写法：只在每条指令处理完后更新一次 best，却把更新写在了转向分支之后的公共出口。转向不改变坐标，重复更新虽不出错，但一旦把「更新」和「移动」拆开，撞障碍的分支就很容易漏更新。

相似题目

题目	难度	考察点
1041. 困于环中的机器人	中等	同样维护方向索引和左右转，但要判断的是轨迹是否闭合，靠一轮指令后的位移与朝向推结论，不需要任何障碍查询
54. 螺旋矩阵	中等	转向时机不由外部指令给出，而由越界和已访问判定触发，考察边界收缩的写法
59. 螺旋矩阵 II	中等	方向推进用于写入而非追踪答案，重点在下标与填充值的同步递增