车队 II
难度:
标签:
题目描述
代码结果
运行时间: 298 ms, 内存: 49.9 MB
/*
* Approach:
* 1. Similar to the Java solution but using Java Stream API for a more functional approach.
* 2. We map each pair of consecutive cars to their meeting time or -1 if they don't meet.
*/
import java.util.stream.IntStream;
import java.util.stream.DoubleStream;
public class CarFleetTimeStream {
public static double[] getFleetMeetingTimes(int[][] cars) {
int n = cars.length;
return IntStream.range(0, n)
.mapToDouble(i -> {
if (i == n - 1) return -1.0;
int pos1 = cars[i][0], speed1 = cars[i][1];
int pos2 = cars[i + 1][0], speed2 = cars[i + 1][1];
return speed1 <= speed2 ? -1.0 : (double) (pos2 - pos1) / (speed1 - speed2);
})
.toArray();
}
}
解释
方法:
题解采用了单调栈的方法从右向左遍历车辆数组,通过比较速度和位置关系计算车辆相遇时间。具体来说,对于每一辆车,先将速度比当前车快或相等的车从栈中移除,这是因为这些车会比当前车先远离,难以相遇。接下来计算当前车与栈中车辆的相遇时间,如果当前车在相遇时间内能追上前车,且这个时间不晚于前车的相遇时间(如果有的话),则当前车的相遇时间就是这个时间。此后,将当前车加入栈中,因为可能有后面的车需要与之比较。这样一来,每辆车的计算都依赖于它前面的车的状态,通过栈来维持这种依赖关系,使得问题得以有效解决。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
栈中为什么要移除速度不低于当前车的车辆?他们之间有可能相遇吗?
▷🦆
如果当前车的速度比所有栈中车辆都慢,那么它的答案为什么直接是 `-1.0`?能否通过数学证明解释这一点?
▷🦆
单调栈在这个问题中扮演了什么角色?为什么选择从右向左而不是从左向右遍历车辆数组?
▷