LeetCode 题解工作台
机器人碰撞
现有 n 个机器人，编号从 1 开始，每个机器人包含在路线上的位置、健康度和移动方向。 给你下标从 0 开始的两个整数数组 positions 、 healths 和一个字符串 directions （ directions[i] 为 'L' 表示 向左 或 'R' 表示 向右 ）。 positio…
4
题型
7
代码语言
3
相关题
当前训练重点
困难 · 栈·状态
答案摘要
我们首先将机器人按照位置从小到大排序，用一个数组 存储排序后的机器人编号。然后我们使用一个栈来模拟碰撞过程： 1. 从左到右遍历 中的机器人编号 ，如果 是向右移动，则将 入栈。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
现有 n 个机器人，编号从 1 开始，每个机器人包含在路线上的位置、健康度和移动方向。
给你下标从 0 开始的两个整数数组 positions、healths 和一个字符串 directions（directions[i] 为 'L' 表示 向左 或 'R' 表示 向右）。 positions 中的所有整数 互不相同 。
所有机器人以 相同速度 同时 沿给定方向在路线上移动。如果两个机器人移动到相同位置，则会发生 碰撞 。
如果两个机器人发生碰撞，则将 健康度较低 的机器人从路线中 移除 ，并且另一个机器人的健康度 减少 1 。幸存下来的机器人将会继续沿着与之前 相同 的方向前进。如果两个机器人的健康度相同，则将二者都从路线中移除。
请你确定全部碰撞后幸存下的所有机器人的 健康度 ，并按照原来机器人编号的顺序排列。即机器人 1 （如果幸存）的最终健康度，机器人 2 （如果幸存）的最终健康度等。 如果不存在幸存的机器人，则返回空数组。
在不再发生任何碰撞后，请你以数组形式，返回所有剩余机器人的健康度（按机器人输入中的编号顺序）。
注意：位置 positions 可能是乱序的。
示例 1：
输入：positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR" 输出：[2,17,9,15,10] 解释：在本例中不存在碰撞，因为所有机器人向同一方向移动。所以，从第一个机器人开始依序返回健康度，[2, 17, 9, 15, 10] 。
示例 2：
输入：positions = [3,5,2,6], healths = [10,10,15,12], directions = "RLRL" 输出：[14] 解释：本例中发生 2 次碰撞。首先，机器人 1 和机器人 2 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。接下来，机器人 3 和机器人 4 将会发生碰撞，由于机器人 4 的健康度更小，则它会被移除，而机器人 3 的健康度变为 15 - 1 = 14 。仅剩机器人 3 ，所以返回 [14] 。
示例 3：
输入：positions = [1,2,5,6], healths = [10,10,11,11], directions = "RLRL" 输出：[] 解释：机器人 1 和机器人 2 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。机器人 3 和机器人 4 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。所以返回空数组 [] 。
提示：
1 <= positions.length == healths.length == directions.length == n <= 1051 <= positions[i], healths[i] <= 109directions[i] == 'L'或directions[i] == 'R'positions中的所有值互不相同
解题思路
方法一：栈模拟
我们首先将机器人按照位置从小到大排序，用一个数组 存储排序后的机器人编号。然后我们使用一个栈来模拟碰撞过程：
- 从左到右遍历 中的机器人编号 ，如果 是向右移动，则将 入栈。
- 如果 是向左移动，则与栈顶的向右移动的机器人发生碰撞，直到栈为空或当前机器人被移除。
- 如果栈顶机器人健康度大于当前机器人，则当前机器人被移除，栈顶机器人健康度减 1。
- 如果栈顶机器人健康度小于当前机器人，则栈顶机器人被移除，当前机器人健康度减 1，并继续与新的栈顶机器人发生碰撞。
- 如果两者健康度相同，则两者都被移除。
最后我们返回所有健康度大于 0 的机器人健康度。
时间复杂度 ，空间复杂度 。其中 是机器人的数量。
class Solution:
def survivedRobotsHealths(self, positions, healths, directions):
idx = sorted(range(len(positions)), key=lambda i: positions[i])
stk = []
for i in idx:
if directions[i] == "R":
stk.append(i)
continue
while stk and healths[i]:
j = stk[-1]
if healths[j] > healths[i]:
healths[j] -= 1
healths[i] = 0
elif healths[j] < healths[i]:
healths[i] -= 1
healths[j] = 0
stk.pop()
else:
healths[i] = healths[j] = 0
stk.pop()
break
return [h for h in healths if h > 0]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \cdot \log n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Candidate should demonstrate an understanding of stack-based state management.
- question_mark
Look for clarity in how the stack is used to handle the robots and their health adjustments.
- question_mark
Ensure the candidate emphasizes sorting the robots by position to process collisions correctly.
常见陷阱
外企场景- error
Failing to sort the robots correctly before processing collisions can lead to incorrect results.
- error
Not properly handling edge cases where robots collide with equal health, resulting in both being removed.
- error
Mismanaging the stack and leaving robots unprocessed or miscalculating their final health.
进阶变体
外企场景- arrow_right_alt
Change the robot movement speed or direction and observe how the solution adapts to different constraints.
- arrow_right_alt
Consider introducing more complex robot interaction rules, such as robots with special abilities or health modifiers.
- arrow_right_alt
Introduce obstacles in the robot path that block movement and modify how collisions are handled.