题目描述
现有 n
个机器人,编号从 1
开始,每个机器人包含在路线上的位置、健康度和移动方向。
给你下标从 0 开始的两个整数数组 positions
、healths
和一个字符串 directions
(directions[i]
为 'L'
表示 向左 或 'R'
表示 向右)。positions
中的所有整数 互不相同。
所有机器人以 相同速度 同时 沿给定方向在路线上移动。如果两个机器人移动到相同位置,则会发生 碰撞。
如果两个机器人发生碰撞,则将 健康度较低 的机器人从路线中 移除,并且另一个机器人的健康度 减少 1。幸存下来的机器人将会继续沿着与之前 相同 的方向前进。如果两个机器人的健康度相同,则将二者都从路线中移除。
请你确定全部碰撞后幸存下的所有机器人的 健康度,并按照原来机器人编号的顺序排列。即机器人 1 (如果幸存)的最终健康度,机器人 2 (如果幸存)的最终健康度等。如果不存在幸存的机器人,则返回空数组。
在不再发生任何碰撞后,请你以数组形式,返回所有剩余机器人的健康度(按机器人输入中的编号顺序)。
注意:位置 positions
可能是乱序的。
样例
输入:positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"
输出:[2,17,9,15,10]
解释:
在本例中不存在碰撞,因为所有机器人向同一方向移动。
所以,从第一个机器人开始依序返回健康度,[2, 17, 9, 15, 10]。
输入: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]。
输入: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'
或directions[i] == 'R'
positions
中的所有值互不相同。
算法
(排序,栈模拟) $O(n \log n)$
- 将机器人按照位置从小到大排序,然后使用栈模拟移动过程。
- 如果当前机器人是向右移动的,则进栈。
- 否则,比对当前机器人与栈顶机器人的健康度,如果当前机器人的健康度小于栈顶机器人的健康度,则栈顶机器人的健康度减一;如果当前机器人的健康度等于栈顶机器人的健康度,则栈顶机器人出栈。
- 否则,栈顶机器人出栈,当前机器人健康度减一,并继续比对新的栈顶机器人的情况。
- 被移除的机器人可以标记健康度为 $-1$,便于最终输出答案。
- 最终找到健康度不为 $-1$ 的机器人输出答案
时间复杂度
- 排序的时间复杂度为 $O(n \log n)$。
- 排序后,每个机器人最多进栈一次,出栈一次。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储排序的下标数组,排序的系统栈,栈和答案。
C++ 代码
class Solution {
public:
vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths,
string directions
) {
const int n = positions.size();
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y) {
return positions[x] < positions[y];
});
stack<int> s;
for (int i : id) {
if (directions[i] == 'R') {
s.push(i);
continue;
}
while (!s.empty()) {
if (healths[i] < healths[s.top()]) {
healths[i] = -1;
--healths[s.top()];
break;
}
if (healths[i] == healths[s.top()]) {
healths[i] = healths[s.top()] = -1;
s.pop();
break;
}
--healths[i];
healths[s.top()] = -1;
s.pop();
}
}
vector<int> ans;
for (int x : healths)
if (x != -1)
ans.push_back(x);
return ans;
}
};