机器人碰撞

难度: Hard

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

Submission

运行时间: 169 ms

内存: 31.5 MB

class Solution:
    def survivedRobotsHealths(self, pos: List[int], heal: List[int], dst: str) -> List[int]:
        n = len(pos)
        a = sorted(range(n), key = lambda x: pos[x])
        st = []
        for i in a:
            if dst[i] == 'R':
                st.append(i)
                continue
            while st and heal[i]:
                t = st[-1]
                if heal[t] > heal[i]:
                    heal[t] -= 1
                    heal[i] = 0
                elif heal[t] == heal[i]:
                    heal[t] = heal[i] = 0
                else:
                    heal[i] -= 1
                    heal[t] = 0
                if not heal[t]:
                    st.pop()
        return [x for x in heal if x]

Explain

这个算法首先通过对机器人的位置进行排序，以便按照位置顺序处理它们的移动和碰撞。使用一个栈来跟踪所有向右移动的机器人。当遇到向左移动的机器人时，检查栈顶的向右移动的机器人是否与之碰撞。如果发生碰撞，比较两个机器人的健康度，健康度较低的机器人被移除。如果健康度相同，则两者都被移除。栈用于跟踪仍然在移动的机器人，以便可以继续处理后续可能的碰撞。最后，返回所有幸存机器人的健康度。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def survivedRobotsHealths(self, pos: List[int], heal: List[int], dst: str) -> List[int]:
        n = len(pos)
        # 对机器人索引按位置排序
        a = sorted(range(n), key=lambda x: pos[x])
        st = []  # 用于跟踪向右移动的机器人
        for i in a:
            if dst[i] == 'R':
                st.append(i)
                continue
            while st and heal[i]:
                t = st[-1]
                if heal[t] > heal[i]:
                    heal[t] -= 1
                    heal[i] = 0
                elif heal[t] == heal[i]:
                    heal[t] = heal[i] = 0
                else:
                    heal[i] -= 1
                    heal[t] = 0
                if not heal[t]:
                    st.pop()
        return [x for x in heal if x]

Explore

排序机器人的位置是为了按照它们在一维空间中的实际顺序处理它们的移动和相遇。这样做可以确保当处理每个机器人时，所有在它前面的机器人都已经被考虑过，从而正确地模拟它们的相对移动和潜在碰撞。如果不排序，可能会导致处理顺序错误，从而忽略或错误处理某些碰撞。

在代码中用栈来跟踪向右移动的机器人，可以高效管理和处理碰撞。当遇到向左移动的机器人时，算法会检查栈顶的机器人（即最近的向右移动的机器人）。如果存在碰撞，根据它们的健康度处理碰撞结果，并可能从栈中移除机器人。这种方式确保了只要栈中有向右移动的机器人，就会与之后遇到的每一个向左移动的机器人进行碰撞检查，从而保证处理了所有可能的碰撞。

在处理碰撞时，如果栈顶的机器人健康度（向右移动的机器人）高于当前处理的向左移动的机器人，只减少栈顶机器人的健康度而不立即移除它是因为栈顶机器人的剩余健康度仍然可能足以参与后续的碰撞。完全移除一个健康度未耗尽的机器人会导致错误地忽略其对其他机器人的潜在影响。

在这个算法实现中，由于向左移动的机器人在处理时会与栈中的每一个向右移动的机器人（即栈顶开始）进行比较，实际上在逻辑上我们假设所有向左的机器人与它们遇到的任何向右的机器人都会发生碰撞。这是因为我们已经通过位置排序确保了机器人的相对位置，而栈中的机器人则是按照它们在空间中的位置顺序被处理，所以每个向左的机器人在遇到栈中向右的机器人时，都是在模拟一个潜在的碰撞事件。