T2751.机器人碰撞

stack, https://leetcode.cn/problems/robot-collisions/

现有 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 <= 10^5
1 <= positions[i], healths[i] <= 10^9
directions[i] == 'L' 或 directions[i] == 'R'
positions 中的所有值互不相同

这道题是一道典型的栈（Stack）模拟题。

解题思路

移动与碰撞逻辑：
- 所有机器人同时以相同速度移动。这意味着只有相对向内移动的机器人会发生碰撞（即左边的机器人向右移 'R'，右边的机器人向左移 'L'）。
- 同向移动的机器人永远不会碰撞。
- 背向移动的机器人（左边向左，右边向右）永远不会碰撞。
- 当碰撞发生时：健康度低的消失，高的健康度减 1。若相等，则两者都消失。
排序：
- 由于输入的 positions 是乱序的，我们需要先按照机器人位置从小到大进行排序。
- 在排序时，必须记录机器人的原始索引，以便最后能按原始编号顺序输出幸存者的健康度。
栈模拟过程：
- 我们从左向右遍历排序后的机器人。
- 如果遇到向右移动（'R'）的机器人，它可能会与右侧任何向左移动的机器人发生碰撞。我们将它的索引压入栈中。
- 如果遇到向左移动（'L'）的机器人：
  - 如果栈为空，说明它左边没有向右移动的机器人，它会一直向左走，安全生存。
  - 如果栈不为空，它会与栈顶（即它左侧最近的一个向右移的机器人）发生碰撞。
  - 碰撞处理：根据健康度比较结果，决定谁消失或健康度减 1。如果 'L' 机器人赢了且健康度仍大于 0，它会继续向左看，去碰撞栈里的下一个 'R' 机器人。
返回结果：
- 遍历结束后，留在栈中的 'R' 机器人和已经穿过碰撞区留在原数组中的 'L' 机器人就是幸存者。
- 按照原始索引顺序过滤并输出 healths 数组中大于 0 的值。
代码实现

python

from typing import List

class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        n = len(positions)
        # 1. 记录原始索引并按位置排序
        # indices 存储的是 0 到 n-1，排序依据是 positions[i]
        indices = sorted(range(n), key=lambda i: positions[i])
        
        stack = []  # 栈中存储向右移动 ('R') 的机器人的原始索引
        
        for i in indices:
            if directions[i] == 'R':
                # 向右走的机器人先入栈，等待与之后向左走的机器人碰撞
                stack.append(i)
            else:
                # 当前机器人向左走 ('L')，尝试与栈中所有向右走的机器人碰撞
                while stack and healths[i] > 0:
                    top_idx = stack[-1]
                    
                    if healths[top_idx] > healths[i]:
                        # 栈顶机器人赢了
                        healths[top_idx] -= 1
                        healths[i] = 0  # 当前机器人消失
                        # 栈顶机器人继续留在栈中（它可能还会撞后面来的 'L'）
                    elif healths[top_idx] < healths[i]:
                        # 当前 'L' 机器人赢了
                        healths[i] -= 1
                        healths[top_idx] = 0 # 栈顶机器人消失
                        stack.pop()
                    else:
                        # 健康度相同，同归于尽
                        healths[i] = 0
                        healths[top_idx] = 0
                        stack.pop()
                        
        # 2. 按照原始编号顺序，返回健康度大于 0 的机器人
        return [h for h in healths if h > 0]

复杂度分析

时间复杂度： $O (N \log N)$ 。
- 排序需要 $O (N \log N)$ 。
- 遍历机器人时，每个机器人最多入栈一次、出栈一次，栈操作的总时间复杂度为 $O (N)$ 。
- 最后过滤结果需要 $O (N)$ 。
空间复杂度： $O (N)$ 。
- 用于存储索引数组 indices 和辅助栈 stack。

T2751.机器人碰撞 ​

T2751.机器人碰撞