846. The Water Standing Over Each Bar
A row of n bars of width 1 has heights h[0] ... h[n-1]. It rains until nothing more can be
held, and water at the open ends runs off.
Print the DEPTH of water standing over each bar, all n values on one line separated by single
spaces. A bar that holds nothing reports 0.
0 1 0 2 1 0 1 3 2 1 2 1 -> 0 0 1 0 1 2 1 0 0 1 0 0
4 2 0 3 2 5 -> 0 2 4 1 2 0
3 0 3 0 3 0 3 -> 0 3 0 3 0 3 0
Problem 170 asks for the TOTAL, one number. This asks where the water actually sits, which is a harder thing for the stack method to produce and the reason this problem exists.
## The stack fills water in horizontal slabs
Walk left to right with a stack of positions kept DECREASING in height. When h[i] is taller
than the top, that top is the FLOOR of a basin whose right wall is i and whose left wall is
whatever lies below it on the stack.
while the stack is non-empty and h[top] < h[i]:
floor = pop
if the stack is now empty: stop, water runs off the left
left = the new top
depth = min(h[left], h[i]) - h[floor]
that depth of water covers every position from left+1 to i-1
push i
Each pop adds one horizontal SLAB, not one column. A deep basin is filled by several slabs, one per pop, stacked on top of each other as the walls get taller.
## Why the slab really covers that whole range
Every position strictly between left and i has already been popped, and that can only have happened because its height is
at most h[floor]. So at the moment of this pop, the whole range left+1 .. i-1 has already
been filled to level h[floor] by earlier slabs, and the new slab raises all of it to
min(h[left], h[i]) uniformly. That is what makes a rectangle the correct shape.
## Turning slabs into per-bar depths
Adding depth to every position in a range would make the algorithm O(n^2) on a wide basin.
Use a DIFFERENCE ARRAY instead: record diff[left+1] += depth and diff[i] -= depth, and at the
end run a prefix sum over diff to recover each bar's total depth.
That is the whole trick of this problem: the stack decides WHICH rectangles, the difference array applies them in constant time each.
## Why it is linear
At most n pops, each producing at most one range update of two array writes, plus one prefix
sum. Total O(n).
## What to check
The pop must stop when the stack empties: a basin with no left wall is open to the sky and the
water runs off, which is why 1 2 3 4 5 is all zeros.
The depth can be zero when the floor is level with the shorter wall, and the range can be empty
when i = left + 1; both cases must simply add nothing rather than writing a negative value.
The running total can reach 10^9 per bar, and the difference array accumulates several slabs at
the same index, so 64-bit values are needed.
## Related problems
Problem 170 reports only the total. Problem 838 measures the same left and right boundaries for a different purpose.
## Sizes and widths
Heights reach 10^9, so every depth does too, which sits just inside a signed 32 bit integer and
leaves no headroom at all. The difference array holds signed values of the same magnitude. Use 64
bits throughout; it costs nothing and removes the question.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ h[i] ≤ 10^9`
Input
The first line contains one integer n.
The second line contains n integers h[0] ... h[n-1].
Output
Print n integers on one line, separated by single spaces: the depth of water standing over each bar, in input order, with 0 where nothing is held. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.