LeetCode 2751. 机器人碰撞 详细技术解析（栈模拟+排序）
LeetCode 2751. 机器人碰撞 详细技术解析（栈模拟+排序）
一、题目描述
现有 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] 。核心分析：所有机器人均向右移动（directions 全为 ‘R’），方向一致，不会出现相向而行的情况，因此无碰撞，直接返回所有机器人的原始健康度。
示例 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] 。核心分析：先按位置排序机器人，再模拟碰撞过程：
排序后机器人顺序：位置 2（机器人3，R）、位置3（机器人1，R）、位置5（机器人2，L）、位置6（机器人4，L）；
机器人1（R）与机器人2（L）碰撞，健康度均为10，同归于尽；
机器人3（R）与机器人4（L）碰撞，机器人3健康度15＞12，机器人4被移除，机器人3健康度变为14；
最终仅剩机器人3，按原始编号顺序返回 [14]。
示例 3
输入：positions = [1,2,5,6], healths = [10,10,11,11], directions = "RLRL" 输出：[] 解释：机器人 1 和机器人 2 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。机器人 3 和机器人 4 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。所以返回空数组 [] 。核心分析：排序后机器人顺序：位置1（机器人1，R）、位置2（机器人2，L）、位置5（机器人3，R）、位置6（机器人4，L）；两组碰撞均为健康度相同，全部同归于尽，无幸存者。
三、提示信息
1 ≤ positions.length == healths.length == directions.length == n ≤ 10⁵（数据量较大，算法需保证 O(n log n) 复杂度）；
1 ≤ positions[i], healths[i] ≤ 10⁹（健康度和位置数值较大，无需考虑溢出问题）；
directions[i] == ‘L’ 或 directions[i] == ‘R’；
positions 中的所有值互不相同。
四、解题思路（栈模拟 + 排序）
4.1 核心问题拆解
碰撞前提：只有向右（R）和向左（L）相向而行的机器人才会碰撞，同向机器人不会碰撞；
碰撞顺序：机器人速度相同，位置相邻且相向的机器人优先碰撞，碰撞后幸存机器人继续移动，可能引发后续碰撞；
位置乱序处理：positions 可能乱序，需先按位置升序排序，才能从左到右模拟碰撞过程；
结果输出：最终需按机器人原始编号顺序返回健康度，因此排序时需保留原始索引。
4.2 算法核心思想
采用栈模拟处理碰撞过程，核心逻辑如下：
预处理：将每个机器人的位置、健康度、方向、原始索引打包，按位置升序排序；
栈的作用：维护当前“待碰撞”的向右（R）机器人（只有向右的机器人才可能与后续向左的机器人碰撞）；
遍历排序后的机器人：
若当前机器人方向为 ‘R’：直接入栈，等待后续可能的碰撞；
若当前机器人方向为 ‘L’：与栈顶的向右（R）机器人循环碰撞，直到栈为空、栈顶不是向右机器人，或当前机器人被撞毁。
碰撞规则执行：每次碰撞严格按照“健康度低的被移除，幸存者健康度减1；健康度相同则同归于尽”的规则处理；
结果整理：栈中剩余的机器人即为幸存者，按原始索引排序后，提取健康度并按原始编号顺序输出。
4.3 为什么用栈？
栈的“后进先出”特性，恰好匹配碰撞的优先级：后续遇到的向左（L）机器人，只会与最近的向右（R）机器人（栈顶元素）碰撞。一旦栈顶机器人被撞毁，再与新的栈顶（更远的向右机器人）碰撞，符合实际碰撞逻辑。
该思路是经典“行星碰撞”问题的变种，区别仅在于碰撞后的健康度变化规则，核心逻辑完全复用栈模拟的思想。
五、完整可提交代码
from typing import List class Solution: def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]: n = len(positions) # 打包机器人信息：[位置, 健康度, 方向, 原始索引] # 原始索引用于最终按输入顺序输出结果 robots = [[positions[i], healths[i], directions[i], i] for i in range(n)] # 按位置从小到大排序，确保从左到右模拟碰撞顺序 robots.sort() # 栈：存储待碰撞的机器人，元素格式 [健康度, 原始索引, 方向] # 栈中主要存储向右(R)的机器人，向左(L)的机器人仅在未碰撞时入栈 stack = [] for p, h, d, idx in robots: if d == 'R': # 向右的机器人直接入栈，等待后续可能的碰撞 stack.append([h, idx, d]) continue # 当前机器人方向为L，开始与栈顶的R机器人碰撞 survive = True # 标记当前L机器人是否能幸存 while stack and stack[-1][2] == 'R': # 取出栈顶的R机器人信息 top_h, top_idx, top_d = stack[-1] if top_h > h: # 栈顶R机器人健康度更高，幸存并减1，当前L机器人被移除 stack[-1][0] -= 1 survive = False break elif top_h < h: # 当前L机器人健康度更高，栈顶R机器人被移除，当前L机器人健康度减1，继续碰撞 stack.pop() h -= 1 else: # 两者健康度相同，同归于尽 stack.pop() survive = False break # 若当前L机器人幸存，加入栈（后续不会再碰撞，因后续机器人位置更大，同向或背向） if survive: stack.append([h, idx, d]) # 按原始索引排序，确保输出顺序与输入时的机器人编号一致 stack.sort(key=lambda x: x[1]) # 提取幸存机器人的健康度，按原始编号顺序返回 return [item[0] for item in stack]六、代码逐行解析
6.1 预处理与排序
robots = [[positions[i], healths[i], directions[i], i] for i in range(n)] robots.sort()将每个机器人的核心信息（位置、健康度、方向、原始索引）打包成列表，再按位置升序排序。排序是模拟碰撞的前提，确保我们能从左到右依次处理机器人，符合实际移动碰撞逻辑。
6.2 栈初始化与遍历处理
stack = [] for p, h, d, idx in robots: if d == 'R': stack.append([h, idx, d]) continue初始化空栈，遍历排序后的机器人：若机器人方向为 ‘R’，直接入栈，因为它只会与后续向左的机器人碰撞，当前无碰撞风险。
6.3 碰撞逻辑处理
survive = True while stack and stack[-1][2] == 'R': top_h, top_idx, top_d = stack[-1] if top_h > h: stack[-1][0] -= 1 survive = False break elif top_h < h: stack.pop() h -= 1 else: stack.pop() survive = False break当遇到向左（L）的机器人时，进入碰撞循环：
survive 标记当前L机器人是否能幸存，初始为 True；
循环条件：栈非空且栈顶是向右（R）的机器人（只有这种情况才会碰撞）；
栈顶R健康度 > 当前L健康度：R幸存（健康度减1），L被移除（survive设为False），退出循环；
栈顶R健康度 < 当前L健康度：R被移除（弹出栈），L健康度减1，继续与新栈顶碰撞；
健康度相等：两者同归于尽（弹出栈顶，survive设为False），退出循环。
6.4 幸存者入栈与结果整理
if survive: stack.append([h, idx, d]) stack.sort(key=lambda x: x[1]) return [item[0] for item in stack]若L机器人在碰撞后幸存，将其入栈（后续不会再碰撞）；遍历结束后，按原始索引排序栈中幸存者，提取健康度并返回，确保输出顺序与输入时的机器人编号一致。
七、复杂度分析
时间复杂度：O(n log n)。核心耗时为机器人按位置排序（O(n log n)），每个机器人最多入栈、出栈各一次，碰撞处理的总耗时为 O(n)，整体复杂度由排序主导。
空间复杂度：O(n)。用于存储机器人列表和栈，最坏情况下（所有机器人同向，无碰撞），栈会存储所有机器人，空间复杂度为 O(n)。
八、常见问题与避坑点
忘记保留原始索引：直接按排序后的顺序输出，导致结果顺序错误。解决方案：打包机器人信息时，必须保留原始索引，最终按原始索引排序。
碰撞逻辑遗漏“连续碰撞”：只处理一次碰撞就退出循环，导致L机器人健康度减少后，未与新的栈顶R机器人碰撞。解决方案：用while循环，直到栈为空、栈顶不是R，或当前机器人被撞毁。
栈中存储信息不完整：只存储健康度和索引，无法判断方向，导致碰撞逻辑错误。解决方案：栈中需存储健康度、原始索引、方向，确保能区分机器人移动方向。
数据量适配问题：忽略n≤10⁵的提示，使用O(n²)复杂度的算法（如暴力模拟所有碰撞），导致超时。解决方案：必须使用栈模拟，确保O(n log n)复杂度。
九、总结
本题的核心是“栈模拟碰撞 + 排序预处理”，本质是对经典行星碰撞问题的变形，重点在于理解“相向而行才会碰撞”和“最近的R机器人优先碰撞”这两个核心点。
解题关键步骤：排序（保证碰撞顺序）→ 栈模拟（处理连续碰撞）→ 按原始索引排序（保证输出顺序）。代码逻辑简洁，复杂度适配题目数据量，可直接提交AC。
掌握该思路后，可轻松解决各类“碰撞模拟”类题目，如小行星碰撞、汽车碰撞等，核心逻辑完全可复用。