834. Buildings With a Clear View

A street has n buildings in a row, with heights h[0] ... h[n-1]. Everyone looks to the RIGHT, towards the end of the street.

A building has a clear view if no building to its right is strictly taller than it. An equal height does NOT block the view.

Print the 1-based positions of the buildings with a clear view, in increasing order, separated by single spaces. The last building always qualifies, so there is always at least one answer.

4 2 3 1 -> 1 3 4 1 2 3 4 -> 4 2 2 2 2 -> 1 2 3 4

In the first row, building 1 stands at height 4 and nothing after it reaches 4, so it sees out. Building 2 stands at height 2 and the 3 after it blocks the view. In the third row every building is the same height, and since equal does not block, all four see out.

## Why the obvious version is quadratic, and what a running maximum gives you

Comparing each building against everything to its right is O(n^2). A right-to-left sweep with a running maximum fixes that in O(n), and it is a perfectly good answer.

The stack is worth learning anyway, because it produces the same set left to right, and because the survivors on the stack ARE the answer rather than something that has to be reversed afterwards. Sweeping right to left collects the positions backwards, so they need reversing before printing; the stack does not.

## The stack, and why it decreases

Walk left to right. Before pushing i, pop every position on the stack that is strictly shorter than h[i], because h[i] has just blocked it forever. Then push i.

The stack therefore holds positions in non-increasing height order from the bottom up. When the scan ends, exactly the positions that were never blocked are still there, in increasing index order, which is the order the answer wants.

Decreasing is the right direction because a taller building to the right is what disqualifies you.

## Why a popped building can never come back

If h[i] > h[j] for i > j, then j is blocked by i and stays blocked no matter what comes later: removing a blocker from the future is not something the rest of the row can do. So one pop per index is all that is ever needed.

## The comparison that decides the flat case

Pop on h[top] < h[i], strictly. Change it to <= and equal buildings start blocking each other, so 2 2 2 2 answers only 4. The statement says strictly taller, so the test is strict.

## Related problems

Problem 154 asks which value blocks you rather than whether anything does, and problem 835 asks how many buildings each one can see before the view closes.

## Sizes and widths

Heights reach 10^9, and the answers are positions, at most n. Comparisons alone never overflow, so 32 bits is sufficient throughout.

## Cost

Time O(n). Space O(n), and in the worst case (a row that only falls) the stack holds everything.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ h[i] ≤ 10^9`