Car Fleet II LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<double> getCollisionTimes(vector<vector<int>> &cars) {
4
    int n = cars.size();
5
    vector<double> res(n, -1.0);
6
    stack<int> st; // for storing indices
7
    for (int i = n - 1; i >= 0; i--) {
8
      // traversing from back if someone has greater speed and ahead of lesser
9
      // speed car it will always be ahead
10
      while (!st.empty() && cars[st.top()][1] >= cars[i][1]) st.pop();
11
      while (!st.empty()) // for lesser speed car ahead of greater spped car
12
      {
13
        double collision_time =
14
            (double)(cars[st.top()][0] - cars[i][0]) / (cars[i][1] - cars[st.top()][1]);
15
        if (collision_time <= res[st.top()] || res[st.top()] == -1) {
16
          res[i] = collision_time;
17
          break;
18
        }
19
        st.pop();
20
      }
21

22
      st.push(i);
23
    }
24
    return res;
25
  }
26
};