2751-机器人碰撞

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

现有 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 中的所有值互不相同

本题思路和 735. 行星碰撞 是一样的。

用列表 toLeft 维护向左的机器人，用栈 st 维护向右的机器人。

按照 positions}[i] 从小到大排序。遍历机器人，如果遇到一个向左的机器人 p，分类讨论：

  • 如果 p 的健康度小于栈顶，那么栈顶的健康度减一。
  • 如果 p 的健康度等于栈顶，那么移除栈顶。
  • 如果 p 的健康度大于栈顶，那么移除栈顶，将 p 的健康度减一后加入 toLeft。
  • 请注意，如果健康度减一，那么在减一之前，健康度一定是大于 1 的，不存在健康度减为 0 的情况。

最后剩余的就是 toLeft 和 st 中的机器人，合并，按照编号排序后，返回健康度列表。

代码实现时，也可以直接在 healths 上修改，最后返回 healths 中的正数。

视频讲解见【周赛 351】 第四题，欢迎点赞！

[sol-Python3]
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
class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        n = len(positions)
        a = sorted(zip(range(n), positions, healths, directions), key=lambda p: p[1])
        to_left = []
        st = []
        for i, _, h, d in a:
            if d == 'R':  # 向右，存入栈中
                st.append([i, h])
                continue
            # 当前机器人向左，与栈中向右的机器人碰撞
            while st:
                top = st[-1]
                if top[1] > h:  # 栈顶的健康度大
                    top[1] -= 1
                    break
                if top[1] == h:  # 健康度一样大
                    st.pop()
                    break
                h -= 1  # 当前机器人的健康度大
                st.pop()  # 移除栈顶
            else:  # while 循环没有 break，说明当前机器人把栈中的全部撞掉
                to_left.append([i, h])
        to_left += st  # 合并剩余的机器人
        to_left.sort(key=lambda p: p[0])  # 按编号排序
        return [h for _, h in to_left]
[sol-Java]
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
class Solution {
    public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
        int n = positions.length;
        var id = new Integer[n];
        for (int i = 0; i < n; ++i) id[i] = i;
        Arrays.sort(id, (i, j) -> positions[i] - positions[j]);

        var st = new ArrayDeque<Integer>();
        for (int i : id) {
            if (directions.charAt(i) == 'R') { // 向右，存入栈中
                st.push(i);
                continue;
            }
            // 向左，与栈中向右的机器人碰撞
            while (!st.isEmpty()) {
                int top = st.peek();
                if (healths[top] > healths[i]) { // 栈顶的健康度大
                    healths[top]--;
                    healths[i] = 0;
                    break;
                }
                if (healths[top] == healths[i]) { // 健康度一样大
                    healths[st.pop()] = 0;
                    healths[i] = 0;
                    break;
                }
                healths[st.pop()] = 0;
                healths[i]--; // 当前机器人的健康度大
            }
        }

        var ans = new ArrayList<Integer>();
        for (int h : healths) if (h > 0) ans.add(h);
        return ans;
    }
}
[sol-C++]
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
class Solution {
public:
    vector<int> survivedRobotsHealths(vector<int> &positions, vector<int> &healths, string directions) {
        int n = positions.size(), id[n];
        iota(id, id + n, 0);
        sort(id, id + n, [&](const int i, const int j) {
            return positions[i] < positions[j];
        });

        stack<int> st;
        for (int i: id) {
            if (directions[i] == 'R') { // 向右，存入栈中
                st.push(i);
                continue;
            }
            // 向左，与栈中向右的机器人碰撞
            while (!st.empty()) {
                int top = st.top();
                if (healths[top] > healths[i]) { // 栈顶的健康度大
                    healths[top]--;
                    healths[i] = 0;
                    break;
                }
                if (healths[top] == healths[i]) { // 健康度一样大
                    healths[top] = 0;
                    st.pop(); // 移除栈顶
                    healths[i] = 0;
                    break;
                }
                healths[top] = 0;
                st.pop(); // 移除栈顶
                healths[i]--; // 当前机器人的健康度大
            }
        }

        // 去掉 0
        healths.erase(remove(healths.begin(), healths.end(), 0), healths.end());
        return healths;
    }
};
[sol-Go]
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
func survivedRobotsHealths(positions, healths []int, directions string) []int {
	type data struct {
		i, p, h int
		d       byte
	}
	a := make([]data, len(positions))
	for i, p := range positions {
		a[i] = data{i, p, healths[i], directions[i]}
	}
	sort.Slice(a, func(i, j int) bool { return a[i].p < a[j].p })

	var toLeft, st []data
next:
	for _, p := range a {
		if p.d == 'R' { // 向右，存入栈中
			st = append(st, p)
			continue
		}
		// p 向左，与栈中向右的机器人碰撞
		for len(st) > 0 {
			top := &st[len(st)-1]
			if top.h > p.h { // 栈顶的健康度大
				top.h--
				continue next
			}
			if top.h == p.h { // 健康度一样大
				st = st[:len(st)-1]
				continue next
			}
			p.h-- // p 的健康度大
			st = st[:len(st)-1] // 移除栈顶
		}
		toLeft = append(toLeft, p) // p 把栈中的全部撞掉
	}

	// 合并剩余的机器人，按编号排序
	toLeft = append(toLeft, st...)
	sort.Slice(toLeft, func(i, j int) bool { return toLeft[i].i < toLeft[j].i })
	ans := make([]int, len(toLeft))
	for i, p := range toLeft {
		ans[i] = p.h
	}
	return ans
}

复杂度分析

  • 时间复杂度：\mathcal{O}(n\log n)，其中 n 为 positions 的长度。瓶颈在排序上。
  • 空间复杂度：\mathcal{O}(n)。

相似题目

 Comments
On this page
2751-机器人碰撞