Longest Lit Stretch
Medium · union find
A street has n lamps in a row, at positions 0 to n - 1. At the start every lamp is off.
The list order gives the positions of lamps that are switched on, one at a time, from left to right in the list. No position appears twice, but not every lamp has to be switched on.
A stretch is a group of lit lamps at consecutive positions, with no unlit lamp between them. After each lamp is switched on, work out the length of the longest stretch on the street at that moment.
Return a list with one number per switch-on: the longest stretch right after the first lamp was lit, right after the second, and so on. If order is empty, return an empty list.
Examples
Example 1
Input: n = 5, order = [2, 0, 1, 4, 3]
Output: [1, 1, 3, 3, 5]
Lamps 0, 1 and 2 form a stretch of 3 once lamp 1 is lit. Lamp 4 stands alone. Lighting lamp 3 joins everything into one stretch of 5.
Example 2
Input: n = 6, order = [0, 2, 4, 1, 3, 5]
Output: [1, 1, 1, 3, 5, 6]
The even positions are lit first, so no two lamps touch. Lamp 1 bridges lamps 0 and 2, lamp 3 then joins that stretch to lamp 4, and lamp 5 completes the street.
Example 3
Input: n = 4, order = []
Output: []
Constraints
- 1 <= n <= 10^5
- 0 <= len(order) <= n
- 0 <= order[i] < n
- All values in order are distinct.