跳转至

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] 。

示例 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 <= 105
  • 1 <= positions[i], healths[i] <= 109
  • directions[i] == 'L' 或 directions[i] == 'R'
  • positions 中的所有值互不相同

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def survivedRobotsHealths(
        self, positions: List[int], healths: List[int], directions: str
    ) -> List[int]:
        n = len(positions)
        indices = list(range(n))
        stack = []

        indices.sort(key=lambda i: positions[i])

        for currentIndex in indices:
            if directions[currentIndex] == "R":
                stack.append(currentIndex)
            else:
                while stack and healths[currentIndex] > 0:
                    topIndex = stack.pop()

                    if healths[topIndex] > healths[currentIndex]:
                        healths[topIndex] -= 1
                        healths[currentIndex] = 0
                        stack.append(topIndex)
                    elif healths[topIndex] < healths[currentIndex]:
                        healths[currentIndex] -= 1
                        healths[topIndex] = 0
                    else:
                        healths[currentIndex] = 0
                        healths[topIndex] = 0

        result = [health for health in healths if health > 0]
        return result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
        int n = positions.length;
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }

        Arrays.sort(indices, (i, j) -> Integer.compare(positions[i], positions[j]));

        Stack<Integer> stack = new Stack<>();

        for (int currentIndex : indices) {
            if (directions.charAt(currentIndex) == 'R') {
                stack.push(currentIndex);
            } else {
                while (!stack.isEmpty() && healths[currentIndex] > 0) {
                    int topIndex = stack.pop();

                    if (healths[topIndex] > healths[currentIndex]) {
                        healths[topIndex] -= 1;
                        healths[currentIndex] = 0;
                        stack.push(topIndex);
                    } else if (healths[topIndex] < healths[currentIndex]) {
                        healths[currentIndex] -= 1;
                        healths[topIndex] = 0;
                    } else {
                        healths[currentIndex] = 0;
                        healths[topIndex] = 0;
                    }
                }
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int health : healths) {
            if (health > 0) {
                result.add(health);
            }
        }

        return result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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);
        stack<int> st;

        auto lambda = [&](int i, int j) { return positions[i] < positions[j]; };

        sort(begin(indices), end(indices), lambda);

        vector<int> result;
        for (int currentIndex : indices) {
            if (directions[currentIndex] == 'R') {
                st.push(currentIndex);
            } else {
                while (!st.empty() && healths[currentIndex] > 0) {
                    int topIndex = st.top();
                    st.pop();

                    if (healths[topIndex] > healths[currentIndex]) {
                        healths[topIndex] -= 1;
                        healths[currentIndex] = 0;
                        st.push(topIndex);
                    } else if (healths[topIndex] < healths[currentIndex]) {
                        healths[currentIndex] -= 1;
                        healths[topIndex] = 0;
                    } else {
                        healths[currentIndex] = 0;
                        healths[topIndex] = 0;
                    }
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            if (healths[i] > 0) {
                result.push_back(healths[i]);
            }
        }
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func survivedRobotsHealths(positions []int, healths []int, directions string) []int {
    n := len(positions)
    indices := make([]int, n)
    for i := range indices {
        indices[i] = i
    }

    sort.Slice(indices, func(i, j int) bool {
        return positions[indices[i]] < positions[indices[j]]
    })

    stack := []int{}

    for _, currentIndex := range indices {
        if directions[currentIndex] == 'R' {
            stack = append(stack, currentIndex)
        } else {
            for len(stack) > 0 && healths[currentIndex] > 0 {
                topIndex := stack[len(stack)-1]
                stack = stack[:len(stack)-1]

                if healths[topIndex] > healths[currentIndex] {
                    healths[topIndex] -= 1
                    healths[currentIndex] = 0
                    stack = append(stack, topIndex)
                } else if healths[topIndex] < healths[currentIndex] {
                    healths[currentIndex] -= 1
                    healths[topIndex] = 0
                } else {
                    healths[currentIndex] = 0
                    healths[topIndex] = 0
                }
            }
        }
    }

    result := []int{}
    for _, health := range healths {
        if health > 0 {
            result = append(result, health)
        }
    }

    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function survivedRobotsHealths(
    positions: number[],
    healths: number[],
    directions: string,
): number[] {
    const idx = Array.from({ length: positions.length }, (_, i) => i);
    const stk: number[] = [];

    idx.sort((a, b) => positions[a] - positions[b]);

    for (let iRight of idx) {
        while (stk.length) {
            const iLeft = stk.at(-1)!;
            const havePair = directions[iLeft] === 'R' && directions[iRight] === 'L';
            if (!havePair) break;

            if (healths[iLeft] === healths[iRight]) {
                healths[iLeft] = healths[iRight] = iRight = -1;
                stk.pop();
                break;
            }

            if (healths[iLeft] < healths[iRight]) {
                healths[iLeft] = -1;
                healths[iRight]--;
                stk.pop();
            } else {
                healths[iRight] = iRight = -1;
                healths[iLeft]--;
                break;
            }
        }

        if (iRight !== -1) stk.push(iRight);
    }

    return healths.filter(i => ~i);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {number[]} positions
 * @param {number[]} healths
 * @param {string} directions
 * @return {number[]}
 */
var survivedRobotsHealths = function (positions, healths, directions) {
    const idx = Array.from({ length: positions.length }, (_, i) => i);
    const stk = [];

    idx.sort((a, b) => positions[a] - positions[b]);

    for (let iRight of idx) {
        while (stk.length) {
            const iLeft = stk.at(-1);
            const havePair = directions[iLeft] === 'R' && directions[iRight] === 'L';
            if (!havePair) break;

            if (healths[iLeft] === healths[iRight]) {
                healths[iLeft] = healths[iRight] = iRight = -1;
                stk.pop();
                break;
            }

            if (healths[iLeft] < healths[iRight]) {
                healths[iLeft] = -1;
                healths[iRight]--;
                stk.pop();
            } else {
                healths[iRight] = iRight = -1;
                healths[iLeft]--;
                break;
            }
        }

        if (iRight !== -1) stk.push(iRight);
    }

    return healths.filter(i => ~i);
};

评论