2751. Robot Collisions

Leetcode link

解题思路

这是一道久违的 hard！

题目会给我们若干机器人，每个机器人都有各自的三个属性：位置 position、生命值 health、行走方向 direction

因为机器人有不同的行走方向，所以有些机器人可能会发生碰撞，发生碰撞后有三个结果：

• 往右走的机器人生命值高于往左走的机器人：往右走的机器人生命值 -1；往左走的机器人生命值归 0
• 往右走的机器人生命值低于往左走的机器人：往右走的机器人生命值归 0；往左走的机器人生命值 -1
• 两个机器人生命值相同：同归于尽，两个机器人生命值都归 0

题目要我们求最后的均衡状态（不会在发生碰撞了）下，还活着的机器人的生命值（需要按照一开始的顺序）

题目在我看来有两个难点：

1. 要怎么去模拟碰撞情况
2. 要怎么保证记住一开始机器人的位置

我们先关注第一个难点，要模拟碰撞，我们需要以下几步：

1. 我们需要先把机器人按照位置顺序排序出来
2. 我们从左往右遍历位置，会有两种情况：
   • 遇到了向右走的机器人，这个时候先保存起来（由于碰撞本质上是一种按照先进后出的消耗，所以使用栈来保存）
   • 遇到了向左走的机器人，此时取出栈顶机器人去碰撞（因为栈顶一定是最靠近的向右走机器人）
3. 发生碰撞无非就是上述的三个结果，我们分别进行判断
4. 等到遍历结束，我们把最后生命值大于 0 的机器人收集起来返回

这个步骤中，最难的一步是，我们要怎么保证前期按照位置排序后，后面收集的生命值的顺序呢？

第一步：我们可以引入一个辅助数组 indices，它保存着原来机器人顺序的下标

第二步：我们把 indices 按照 positions 同下标的值从小到大排序，这样我们遍历 indices 就相当于遍历了排序后的 positions, healths, directions

Javascript

/**
 * @param {number[]} positions
 * @param {number[]} healths
 * @param {string} directions
 * @return {number[]}
 */
var survivedRobotsHealths = function(positions, healths, directions) {
    // 辅助数组，用于维持 positions, healths, directions 之间的联系
    const indices = Array.from({length: positions.length}, (_, i) => i);
    // 把辅助函数按照位置从左到右排序
    indices.sort((a, b) => positions[a] - positions[b]);

    // 我们把往右走的 robot 用一个栈维护起来
    const stack = [];
    const result = [];

    for(const i of indices) {
        // 从位置的左到右遍历，如果遇到往右走的 robot 先存起来
        if(directions[i] === 'R') {
            stack.push(i);
            continue;
        }
        // 遇到了往左走的 robot 需要处理一下
        while(healths[i] > 0 && stack.length > 0) {
            const top = stack.pop();

            // 处理发生碰撞的情况
            if(healths[top] > healths[i]) {
                // 情况1: 栈顶往右走的 robot 生命值大于当前往左走的 robot
                healths[top]--;
                healths[i] = 0;
                if(healths[top] > 0) {
                    stack.push(top);
                }
            } else if(healths[top] < healths[i]){
                // 情况2: 栈顶往右走的 robot 生命值比往左走的 robot 低
                healths[top] = 0;
                healths[i]--;
            } else {
                // 情况3: 往左往右的 robot 生命值相同
                healths[top] = 0;
                healths[i] = 0;
            }
        }
    }

    // 把最后结果收集起来
    for(const health of healths) {
        if(health > 0) {
            result.push(health);
        }
    }

    return result;
};