Stacks and Queues Monotonic stack
214. Car Fleet
Some cars drive in the same direction along a one-lane road toward a finish line at mile target. Car i
starts at mile position[i] and drives at a constant speed[i] miles per hour. Return the number of
convoys that cross the finish line.
No car can pass another. When a car catches up with a slower car ahead of it, it stays right behind that car and drives at its speed from then on. A convoy is a group of cars that drive together like this, and a car driving alone is a convoy of one.
A car that catches up with another exactly on the finish line crosses it as part of that convoy.
Example 1
Input: target = 20
position = [5, 12, 0, 16, 9]
speed = [3, 2, 1, 1, 1]
3Explanation: The cars at 16 and 12 both reach the finish at hour 4, so they cross it together. The car at 5 catches the car at 9 at mile 11 and follows it in at hour 11, and the car at 0 crosses alone at hour 20.
Example 2
Input: target = 10, position = [7, 0], speed = [1, 3]
2Explanation: The car at 0 is faster, but it needs 10 / 3 ≈ 3.33 hours and the car at 7 finishes at hour 3. It would catch up only at mile 10.5, past the finish, so the two cars cross separately.
Example 3
Input: target = 6, position = [0, 2, 4], speed = [3, 2, 1]
1Explanation: All three cars reach the finish line at hour 2. They draw level exactly on the line, so they cross it as one convoy.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ position.length ≤ 105speed.length = position.length1 ≤ target ≤ 1090 ≤ position[i] < target1 ≤ speed[i] ≤ 109- All the values of
positionare different.
Clarifying questions
What you would ask an interviewer before writing any code.