Skip to content

1776. Car Fleet II 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct Car {
  int pos;
  int speed;
  double collisionTime;
  Car(int pos, int speed, double collisionTime)
      : pos(pos), speed(speed), collisionTime(collisionTime) {}
};

class Solution {
 public:
  vector<double> getCollisionTimes(vector<vector<int>>& cars) {
    vector<double> ans(cars.size());
    stack<Car> stack;

    for (int i = cars.size() - 1; i >= 0; --i) {
      const int pos = cars[i][0];
      const int speed = cars[i][1];
      while (!stack.empty() && (speed <= stack.top().speed ||
                                getCollisionTime(stack.top(), pos, speed) >=
                                    stack.top().collisionTime))
        stack.pop();
      if (stack.empty()) {
        stack.emplace(pos, speed, INT_MAX);
        ans[i] = -1;
      } else {
        const double collisionTime = getCollisionTime(stack.top(), pos, speed);
        stack.emplace(pos, speed, collisionTime);
        ans[i] = collisionTime;
      }
    }

    return ans;
  }

 private:
  double getCollisionTime(const Car& car, int pos, int speed) {
    return (car.pos - pos) / (double)(speed - car.speed);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Car {
  public int pos;
  public int speed;
  public double collisionTime;
  public Car(int pos, int speed, double collisionTime) {
    this.pos = pos;
    this.speed = speed;
    this.collisionTime = collisionTime;
  }
}

class Solution {
  public double[] getCollisionTimes(int[][] cars) {
    double[] ans = new double[cars.length];
    Deque<Car> stack = new ArrayDeque<>();

    for (int i = cars.length - 1; i >= 0; --i) {
      final int pos = cars[i][0];
      final int speed = cars[i][1];
      while (!stack.isEmpty() &&
             (speed <= stack.peek().speed ||
              getCollisionTime(stack.peek(), pos, speed) >= stack.peek().collisionTime))
        stack.pop();
      if (stack.isEmpty()) {
        stack.push(new Car(pos, speed, Integer.MAX_VALUE));
        ans[i] = -1;
      } else {
        final double collisionTime = getCollisionTime(stack.peek(), pos, speed);
        stack.push(new Car(pos, speed, collisionTime));
        ans[i] = collisionTime;
      }
    }

    return ans;
  }

  private double getCollisionTime(Car car, int pos, int speed) {
    return (double) (car.pos - pos) / (speed - car.speed);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
    ans = []
    stack = []  # (pos, speed, collisionTime)

    def getCollisionTime(
            car: Tuple[int, int, int],
            pos: int, speed: int) -> float:
      return (car[0] - pos) / (speed - car[1])

    for pos, speed in reversed(cars):
      while stack and (
              speed <= stack[-1][1] or getCollisionTime(stack[-1],
                                                        pos, speed) >=
              stack[-1][2]):
        stack.pop()
      if stack:
        collisionTime = getCollisionTime(stack[-1], pos, speed)
        stack.append((pos, speed, collisionTime))
        ans.append(collisionTime)
      else:
        stack.append((pos, speed, math.inf))
        ans.append(-1)

    return ans[::-1]