Monotonic Stack
LC #853Medium
Car Fleet
Monotonic Stack
Problem
Find how many car fleets will arrive at the destination. Cars cannot pass each other.
arraystacksorting
Constraints
- ›1 ≤ n ≤ 10⁵
- ›0 < target ≤ 10⁶
- ›0 ≤ position[i] < target
- ›0 < speed[i] ≤ 10⁶
Example
Input
target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]Output
3Why
The cars starting at 10 and 8 form a fleet. The car at 5 forms a fleet. The cars at 0 and 3 form a fleet. Total 3 fleets.