leetcode
leetcode 1601 ~ 1650
车队 II

车队 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`?能否通过数学证明解释这一点?
如果当前车的速度比所有栈中车辆都慢,那么该车不可能追上任何前面的车辆。因为追上前车的基本条件是后车速度必须大于前车。数学上,如果车i的速度小于车j的速度(车j在车i前面),那么相遇时间计算为 `(pos_j - pos_i) / (speed_i - speed_j)`。由于 `speed_i < speed_j`,分母为负,此时相遇时间计算结果将是一个负数,这在物理意义上表示车i在过去已经被车j超过。因此,当没有任何车的速度比当前车慢时,当前车的答案直接设为 `-1.0`,表示永远不会有相遇发生。
🦆
单调栈在这个问题中扮演了什么角色?为什么选择从右向左而不是从左向右遍历车辆数组?
单调栈在这个问题中用于维持一个车辆索引的序列,其中每辆车的速度都严格小于前一辆车的速度。这种结构使得对于任何新车辆,我们能快速地通过栈顶向下比较找到第一辆可能会相遇的车辆。选择从右向左遍历车辆数组是因为这样可以逐步构建出每辆车的相遇时间。如果从左向右遍历,则前面车辆的相遇信息尚未计算完成,就无法为后续车辆提供必要的信息,从而无法正确计算相遇时间。从右到左遍历确保我们在处理每辆车时,其相遇可能发生的所有“前车”信息已经就绪且存储在栈中。

相关问题