Problem: 853. 车队

思路:

采用单调递减栈，单调栈中存放所有可能的车队到达终点需要的时间。（注意，只保存位置最大的那个车辆，也就是车队中速度最慢的车辆）。我们需要对数组按照postion升序排列，然后从左到右遍历。

如果当前车辆到达时间大于等于栈顶车辆的时间，说明栈顶车辆能追上当前车辆，将栈顶车辆弹出，当前车辆入栈，将它两合并成一个车队。如果当前车辆到达时间小于栈顶车辆达到时间，说明栈顶车辆追不上当前车辆，那么将当前车辆入栈。循环结束后，单调栈的大小就是车队的数量。

复杂度

  • 时间复杂度: O(nlog(n))，瓶颈在排序的复杂度上。当然，也可以采用空间换时间的方法，利用target大小的数组来保存数据。
  • 空间复杂度: O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        int[][] traffic = new int[n][2];
        for (int i = 0; i < n; i ++) {
            traffic[i][0] = position[i];
            traffic[i][1] = speed[i];
        }
        Arrays.sort(traffic, (a, b) -> Integer.compare(a[0], b[0]));
        Deque<Double> st = new ArrayDeque<>();
        for (int i = 0; i < n; i ++) {
            double time = (double) (target - traffic[i][0]) / traffic[i][1];  
            while (!st.isEmpty() && st.peek() <= time) {
                st.pop();
            }
            st.push(time);
        }
        return st.size();
    }
}