Car Fleet
Cars start at distinct positions on a one-lane road heading to a target; each has a constant speed. A car that catches up to a slower car ahead cannot pass and instead joins it as a fleet moving at the slower speed. Count how many fleets arrive at the target.
- 1 ≤ n ≤ 10^5
- 0 < target ≤ 10^6
- 0 ≤ position[i] < target, all distinct
- 0 < speed[i] ≤ 10^6
- Sort by position — the car closest to the target leads
- Compare each car's *arrival time* with the fleet ahead
- A car merges when its time ≤ the time of the fleet in front
Asking, for every element, about the nearest element to its left or right that is larger or smaller is a signal to keep a stack whose values are sorted. Each element is pushed once and popped once, and the moment it is popped you know exactly who its "next greater" is: the element doing the popping.
Sort cars by starting position descending and compute each car's solo arrival time (target - pos) / speed. Walk from the front-most car backward keeping a stack of fleet arrival times. If the current car's time is ≤ the time on the stack top, it catches that fleet and is absorbed; otherwise it starts a new fleet and is pushed. The stack size is the number of fleets.
- Only the previous fleet time matters, so a single running maximum replaces the stack. Simulation over time steps is far slower.