class Solution {
public:
vector<double> getCollisionTimes(vector<vector<int>>& cars) {
}
};
1776. 车队 II
在一条单车道上有 n 辆车，它们朝着同样的方向行驶。给你一个长度为 n 的数组 cars ，其中 cars[i] = [positioni, speedi] ，它表示：
positioni 是第 i 辆车和道路起点之间的距离（单位：米）。题目保证 positioni < positioni+1 。speedi 是第 i 辆车的初始速度（单位：米/秒）。简单起见，所有车子可以视为在数轴上移动的点。当两辆车占据同一个位置时，我们称它们相遇了。一旦两辆车相遇，它们会合并成一个车队，这个车队里的车有着同样的位置和相同的速度，速度为这个车队里 最慢 一辆车的速度。
请你返回一个数组 answer ，其中 answer[i] 是第 i 辆车与下一辆车相遇的时间（单位：秒），如果这辆车不会与下一辆车相遇，则 answer[i] 为 -1 。答案精度误差需在 10-5 以内。
示例 1：
输入：cars = [[1,2],[2,1],[4,3],[7,2]] 输出：[1.00000,-1.00000,3.00000,-1.00000] 解释：经过恰好 1 秒以后，第一辆车会与第二辆车相遇，并形成一个 1 m/s 的车队。经过恰好 3 秒以后，第三辆车会与第四辆车相遇，并形成一个 2 m/s 的车队。
示例 2：
输入：cars = [[3,4],[5,4],[6,3],[9,1]] 输出：[2.00000,1.00000,1.50000,-1.00000]
提示：
1 <= cars.length <= 1051 <= positioni, speedi <= 106positioni < positioni+1原站题解
golang 解法, 执行用时: 332 ms, 内存消耗: 20 MB, 提交时间: 2023-09-25 11:10:54
func getCollisionTimes(cars [][]int) (result []float64) {
n := len(cars)
result = make([]float64, n)
result[n-1] = -1
stack := []int{}
stack = append(stack, n-1)
for i := n-2; i >= 0; i-- {
for len(stack) > 0 && cars[i][1] <= cars[stack[len(stack)-1]][1] {
stack = stack[:(len(stack)-1)]
}
if len(stack) == 0 {
result[i] = -1
stack = append(stack, i)
continue
}
time := float64(cars[stack[len(stack)-1]][0]-cars[i][0])/float64(cars[i][1]-cars[stack[len(stack)-1]][1])
for result[stack[len(stack)-1]] != -1 && time > result[stack[len(stack)-1]]{
stack = stack[:(len(stack)-1)]
time = float64(cars[stack[len(stack)-1]][0]-cars[i][0])/float64(cars[i][1]-cars[stack[len(stack)-1]][1])
}
stack = append(stack, i)
result[i] = time
}
return
}
golang 解法, 执行用时: 292 ms, 内存消耗: 20.3 MB, 提交时间: 2023-09-25 11:10:42
func getCollisionTimes(cars [][]int) []float64 {
n := len(cars)
out := make([]float64, n)
for i := range out {
out[i] = -1.0
}
// 将最后一辆车作为栈底(哨兵)
stk := CarStack{&Car{
cot: math.MaxFloat64,
pos: float64(cars[n-1][0]),
spd: cars[n-1][1],
}}
// 逆序遍历车辆
for i := n - 2; i >= 0; i-- {
pos, spd := float64(cars[i][0]), cars[i][1]
// 1. 若当前车的速度小于等于栈顶，说明无法和初始速度的栈顶车相遇，弹出栈顶
// 2. 若当前车和栈顶车相遇耗时大于等于栈顶车和栈顶车的前一辆车相遇的耗时，说明栈顶车肯定更早和前一辆车相遇，
// 和栈顶车相遇时栈顶车已不是初始速度(已降速，和上一辆车并为一个车队)，必须弹出
for stk.Len() > 0 && (spd <= stk.Top().spd ||
(stk.Top().pos-pos)/(float64(spd-stk.Top().spd)) >= stk.Top().cot) {
stk.Pop()
}
// 当栈已空时，作为新哨兵
cot := math.MaxFloat64
// 若栈未空，计算和上一个车队相遇的时间
if len(stk) > 0 {
cot = (stk.Top().pos - pos) / (float64(spd - stk.Top().spd))
out[i] = cot
}
stk.Push(&Car{
cot: cot,
pos: float64(pos),
spd: spd,
})
}
return out
}
type Car struct {
cot float64 // 和上一辆车的碰撞时间
pos float64 // 发车地和起始地距离
spd int // 初始速度
}
type CarStack []*Car
func (cs CarStack) Len() int { return len(cs) }
func (cs *CarStack) Push(car *Car) { *cs = append(*cs, car) }
func (cs CarStack) Top() *Car { return cs[cs.Len()-1] }
func (cs *CarStack) Pop() *Car {
top := cs.Len() - 1
out := (*cs)[top]
*cs = (*cs)[:top]
return out
}
java 解法, 执行用时: 169 ms, 内存消耗: 92.7 MB, 提交时间: 2023-09-25 11:10:14
class Solution {
public double[] getCollisionTimes(int[][] cars) {
int n = cars.length;
double[] ans = new double[n];
Stack<Integer> stack = new Stack<>();
for(int i=n-1;i>=0;i--){
//栈不为空，需要比较当前车速与栈顶车速
while(!stack.isEmpty()){
//栈顶车速大于当前车速，则当前车追不上栈顶车，但是有可能追上栈顶元素的前一辆车
if(cars[stack.peek()][1]>=cars[i][1]){
stack.pop();
}else{//当前车速大于栈顶车速
//栈顶车撞不上它前面的车，因此，当前车一定可以撞上栈顶车
if(ans[stack.peek()]<0){
break;
}else{//栈顶车能撞上前面的车，需要分情况讨论
//如果当前车能在栈顶车撞上前面车之前就能够撞上栈顶车，则直接撞上去
if(((double)(cars[stack.peek()][0]-cars[i][0]))/((double)(cars[i][1]-cars[stack.peek()][1]))<=ans[stack.peek()]){
break;
}else{//否则的话，当前车就只能撞到栈顶车前面的车了
stack.pop();
}
}
}
}
//初始时，栈为空，前面没车可撞
if(stack.isEmpty()){
ans[i] = -1;
}else{//栈不为空，则撞上栈顶车
ans[i] = ((double)(cars[stack.peek()][0]-cars[i][0]))/((double)(cars[i][1]-cars[stack.peek()][1]));
}
//当前车结果求出后，入栈
stack.push(i);
}
return ans;
}
}
cpp 解法, 执行用时: 580 ms, 内存消耗: 127.1 MB, 提交时间: 2023-09-25 11:09:25
class Solution {
public:
vector<double> getCollisionTimes(vector<vector<int>>& cars) {
int n = cars.size();
vector<double> res(n);
res[n-1] = -1;
stack<int> st;
st.push(n-1);
for(int i = n-2; i >= 0; --i) {
while(st.size()) {
// 此处的详细说明：
// 1. 如果当前车的车速 <= 栈顶车的车速，则当前车永远无法追上栈顶车，因此总是可以 pop 出栈顶车；
// 2. 否则，如果当前车的车速 > 栈顶车：
// 2.1 如果栈顶车的追上更右侧车辆的时间为 -1 (永远追不上)，则不能 pop 出;
// 2.2 否则，则判断在 “理想状态(即栈顶车不会追上更右侧车)”下 ，当前车的追上栈顶车的时间 T
// (也就是下面代码里的式子)，如果 T > res[st.top()](即栈顶车的实际追及时间)，
// 说明不能在右侧车追上更右侧车之前追上，应当 pop；否则能在碰撞前追上。
if(cars[i][1] <= cars[st.top()][1] || (res[st.top()] > 1e-9 && (double)(cars[st.top()][0] - cars[i][0]) / (double)(cars[i][1] - cars[st.top()][1]) > res[st.top()])) {
st.pop();
} else {
break;
}
}
if(st.size()) {
res[i] = (double)(cars[st.top()][0] - cars[i][0]) / (double)(cars[i][1] - cars[st.top()][1]);
st.push(i);
} else {
res[i] = -1;
st.push(i);
}
}
return res;
}
};
python3 解法, 执行用时: 396 ms, 内存消耗: 50.8 MB, 提交时间: 2023-09-25 11:08:56
class Solution:
def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
n = len(cars)
ans = [-1.0] * n
stack = [] # 单调栈，栈底：车速更慢，且初始位置更靠右
for i in range(n-1, -1, -1): # 从右往左遍历
pos, speed = cars[i]
# 弹出栈顶速度更快的车辆，直到栈顶车的速度小于当前车辆
while stack and speed <= cars[stack[-1]][1]:
stack.pop()
# 从栈顶往栈底依次检查当前车是否能及时追上目标车辆
while stack:
j = stack[-1]
time = (cars[j][0] - pos) / (speed - cars[j][1])
if ans[j] < 0 or time <= ans[j]: # 若及时追上了，此即为解
ans[i] = time
break
stack.pop() # 否则弹出栈顶这辆已经检查过的车，准备看下一辆
stack.append(i) # 此时当前车辆的速度一定大于栈顶的车辆，需入栈
return ans
cpp 解法, 执行用时: 600 ms, 内存消耗: 126.1 MB, 提交时间: 2023-09-25 11:08:34
class Solution {
public:
//这道题必须想清楚一点，那就是如果ans[i]有正值，那么一定是cars[i]和某个cars[j]（j>i且speed[j]<speed[i]）发生碰撞
//相撞之后，所谓的融合，其实可以理解为cars[i]消失了，cars[j]状态不变
//所以我们只关注一辆车右边，不关注其左边，它的左边对它没有任何影响。可以考虑从右往左遍历
vector<double> getCollisionTimes(vector<vector<int>>& cars) {
vector<double>ans(cars.size());
//设立一个单调栈，栈底最慢，栈顶最快
stack<int>S;
for(int i=cars.size()-1;i>=0;i--){
while(S.size()){
//如果栈顶比我快，我追不上它，可以考虑等它消失之后我去撞它前面的，所以将它pop
if(cars[S.top()][1]>=cars[i][1])S.pop();
//如果栈顶比我慢，我就决定去碰它了
else{
//如果它不会消失，那我肯定能碰它，break
if(ans[S.top()]<0)break;
//如果它会消失，我需要计算一下在它消失之前能否追上它
double d=ans[S.top()]*(cars[i][1]-cars[S.top()][1]);
//能追上，那我肯定碰它，break
if(d>cars[S.top()][0]-cars[i][0])break;
//追不上，那算了，追它前面的车
else S.pop();
}
}
if(S.empty())ans[i]=-1;
else{
//相对距离除以相对速度
double t=double(cars[S.top()][0]-cars[i][0])/double(cars[i][1]-cars[S.top()][1]);
ans[i]=t;
}
S.push(i);
}
return ans;
}
};