Hard

题目描述

有 n 个 1 索引的机器人，每个机器人都有一个位置、生命值和移动方向。

给你 0 索引的整数数组 positions、healths 和字符串 directions（directions[i] 为 ‘L’ 表示向左，‘R’ 表示向右）。positions 中的所有整数 互不相同。

所有机器人以相同的速度 同时 沿给定方向在直线上开始移动。如果两个机器人移动时处于相同位置，它们将会发生 碰撞。

如果两个机器人发生碰撞，将移除生命值较小的机器人，并且另一个机器人的生命值 减少 1。存活下来的机器人将继续沿着与之前相同的方向前进。如果两个机器人生命值相同，则将移除这两个机器人。

你的任务是确定碰撞后幸存的机器人的生命值，按照原来机器人的顺序返回，即第 1 个机器人的最终生命值（如果幸存）、第 2 个机器人的最终生命值（如果幸存），依此类推。如果没有幸存者，返回空数组。

在不再发生碰撞后，返回包含剩余机器人生命值的数组（按输入中给出的顺序）。

注意： 位置可能是无序的。

示例 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' 或 'R'
  • positions 中所有值互不相同

解题思路

这道题的关键在于模拟机器人的碰撞过程。我们需要按照位置顺序处理机器人，使用栈来跟踪向右移动的机器人，当遇到向左移动的机器人时进行碰撞判断。

解题思路：

  1. 排序处理：首先将机器人按位置排序，这样可以按照它们在直线上相遇的顺序处理碰撞。

  2. 栈模拟碰撞：使用栈存储向右移动且还未碰撞的机器人。当遇到向左移动的机器人时，它会与栈顶的向右移动机器人发生碰撞。

  3. 碰撞逻辑：

    • 向右移动的机器人直接入栈
    • 向左移动的机器人与栈中向右移动的机器人碰撞
    • 根据生命值比较决定哪个机器人被移除，胜利者生命值减1
    • 继续处理直到没有碰撞或当前机器人被消灭

  4. 结果构造：最后按照原始索引顺序返回存活机器人的生命值。

为了保持原始顺序，我们需要记录每个机器人的原始索引，处理完毕后按原始顺序重新组织结果。

代码实现

class Solution {
public:
    vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) {
        int n = positions.size();
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        
        // 按位置排序
        sort(indices.begin(), indices.end(), [&](int i, int j) {
            return positions[i] < positions[j];
        });
        
        vector<int> stack; // 存储向右移动的机器人索引
        
        for (int idx : indices) {
            if (directions[idx] == 'R') {
                stack.push_back(idx);
            } else { // 向左移动
                while (!stack.empty() && healths[idx] > 0) {
                    int rightIdx = stack.back();
                    
                    if (healths[rightIdx] > healths[idx]) {
                        healths[rightIdx]--;
                        healths[idx] = 0;
                    } else if (healths[rightIdx] < healths[idx]) {
                        healths[rightIdx] = 0;
                        healths[idx]--;
                        stack.pop_back();
                    } else { // 生命值相等
                        healths[rightIdx] = 0;
                        healths[idx] = 0;
                        stack.pop_back();
                    }
                }
            }
        }
        
        // 按原始顺序收集结果
        vector<int> result;
        for (int i = 0; i < n; i++) {
            if (healths[i] > 0) {
                result.push_back(healths[i]);
            }
        }
        
        return result;
    }
};

class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        n = len(positions)
        indices = list(range(n))
        
        # 按位置排序
        indices.sort(key=lambda i: positions[i])
        
        stack = []  # 存储向右移动的机器人索引
        
        for idx in indices:
            if directions[idx] == 'R':
                stack.append(idx)
            else:  # 向左移动
                while stack and healths[idx] > 0:
                    right_idx = stack[-1]
                    
                    if healths[right_idx] > healths[idx]:
                        healths[right_idx] -= 1
                        healths[idx] = 0
                    elif healths[right_idx] < healths[idx]:
                        healths[right_idx] = 0
                        healths[idx] -= 1
                        stack.pop()
                    else:  # 生命值相等
                        healths[right_idx] = 0
                        healths[idx] = 0
                        stack.pop()
        
        # 按原始顺序收集结果
        return [healths[i] for i in range(n) if healths[i] > 0]

public class Solution {
    public IList<int> SurvivedRobotsHealths(int[] positions, int[] healths, string directions) {
        int n = positions.Length;
        int[] indices = new int[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        // 按位置排序
        Array.Sort(indices, (i, j) => positions[i].CompareTo(positions[j]));
        
        Stack<int> stack = new Stack<int>(); // 存储向右移动的机器人索引
        
        foreach (int idx in indices) {
            if (directions[idx] == 'R') {
                stack.Push(idx);
            } else { // 向左移动
                while (stack.Count > 0 && healths[idx] > 0) {
                    int rightIdx = stack.Peek();
                    
                    if (healths[rightIdx] > healths[idx]) {
                        healths[rightIdx]--;
                        healths[idx] = 0;
                    } else if (healths[rightIdx] < healths[idx]) {
                        healths[rightIdx] = 0;
                        healths[idx]--;
                        stack.Pop();
                    } else { // 生命值相等
                        healths[rightIdx] = 0;
                        healths[idx] = 0;
                        stack.Pop();
                    }
                }
            }
        }
        
        // 按原始顺序收集结果
        List<int> result = new List<int>();
        for (int i = 0; i < n; i++) {
            if (healths[i] > 0) {
                result.Add(healths[i]);
            }
        }
        
        return result;
    }
}

var survivedRobotsHealths = function(positions, healths, directions) {
    const n = positions.length;
    const indices = Array.from({length: n}, (_, i) => i);
    
    // 按位置排序
    indices.sort((i, j) => positions[i] - positions[j]);
    
    const stack = []; // 存储向右移动的机器人索引
    
    for (const idx of indices) {
        if (directions[idx]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(n)

分析：

  • 时间复杂度：O(n log n) 主要来自排序操作，每个机器人最多被处理一次
  • 空间复杂度：O(n) 用于存储索引数组和栈，以及辅助数据结构

相关题目