There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [positioni, speedi] represents:
positioniis the distance between theithcar and the beginning of the road in meters. It is guaranteed thatpositioni < positioni+1.speediis the initial speed of theithcar in meters per second.
For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the slowest car in the fleet.
Return an array answer, where answer[i] is the time, in seconds, at which the ith car collides with the next car, or -1 if the car does not collide with the next car. Answers within 10-5 of the actual answers are accepted.
Example 1:
Input: cars = [[1,2],[2,1],[4,3],[7,2]] Output: [1.00000,-1.00000,3.00000,-1.00000] Explanation: After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.
Example 2:
Input: cars = [[3,4],[5,4],[6,3],[9,1]] Output: [2.00000,1.00000,1.50000,-1.00000]
Constraints:
1 <= cars.length <= 1051 <= positioni, speedi <= 106positioni < positioni+1
Solution: Monotonic Stack
Key observation: If my speed is slower than the speed of the previous car, not only mine but also all cars behind me will NEVER be able to catch/collide with the previous car. Such that we can throw it away.
Maintain a stack that stores the indices of cars with increasing speed.
Process car from right to left, for each car, pop the stack (throw the fastest car away) if any of the following conditions hold.
1) speed <= stack.top().speed
2) There are more than one car before me and it takes more than to collide the fastest car than time the fastest took to collide.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: vector<double> getCollisionTimes(vector<vector<int>>& cars) { auto collide = [&](int i, int j) -> double { return static_cast<double>(cars[i][0] - cars[j][0]) / (cars[j][1] - cars[i][1]); }; const int n = cars.size(); vector<double> ans(n, -1); stack<int> s; for (int i = n - 1; i >= 0; --i) { while (!s.empty() && (cars[i][1] <= cars[s.top()][1] || (s.size() > 1 && collide(i, s.top()) > ans[s.top()]))) s.pop(); ans[i] = s.empty() ? -1 : collide(i, s.top()); s.push(i); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment