831. How Tall the Stack Gets
Before using a monotonic stack to answer anything, watch one run.
Read n values and walk them left to right, holding a stack. For each value a[i], in order:
pop the top while the stack is not empty and the top is <= a[i]
push a[i]
report the height of the stack
Print the n reported heights on one line, separated by single spaces.
5 3 4 1 2 6 -> 1 2 2 3 3 1
1 2 3 4 5 -> 1 1 1 1 1
5 4 3 2 1 -> 1 2 3 4 5
Trace the first one. 5 pushes onto nothing, height 1. 3 does not reach 5, so it sits on top,
height 2. 4 pops the 3 and sits on the 5, height 2 again. 1 and 2 build back up to 3, and
then 6 clears everything, height 1.
## What the height actually counts
After a[i] has been processed, the stack holds exactly those earlier values that nothing since
has reached. Formally, index j <= i survives if and only if
a[j] > a[t] for every t with j < t <= i
so the height is the number of positions in a[0..i] that are strictly greater than everything
after them inside that prefix. Reading the row from the right, those are the values you would see
before the view is blocked.
## Why the popped ones never come back
A value is popped only when something at least as large arrives to its right. From that moment on, any future question of the form "is there something bigger to the left of me" is answered by the newer, larger, closer value instead. The popped one is dominated on both counts, size and distance, so it can never be the answer to anything again. That is why throwing it away is safe, and it is why the stack is allowed to forget.
## Why this costs O(n) and not O(n^2)
The inner while can pop many values in one step, so the worst single step is O(n). But each
index is pushed exactly once, and once popped it is gone, so across the whole run there are at
most n pops in total. The sum of the work is O(n) even though no individual step is bounded
by a constant. This is the counting argument behind every problem in this topic.
## The comparison to get right
The rule above pops on <=, so an arriving value removes an earlier EQUAL one. Change it to <
and equal values stack up instead: 3 3 3 3 reports 1 1 1 1 under <= and 1 2 3 4 under
<. Neither is wrong in general; they answer different questions. Here the rule is <=.
## Sizes and widths
Values reach 10^9, but nothing here is ever added or multiplied: the only output is a stack
height, which is at most n. So 32 bits is enough everywhere, and this is the last problem in the
block for which that is true.
## Cost
Time O(n). Space O(n), the stack in the worst case holds everything.
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a[i] ≤ 10^9`
Input
The first line contains one integer n.
The second line contains n integers a[0] ... a[n-1].
Output
Print n integers on one line, separated by single spaces: the height of the stack after each value has been pushed, in input order. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.