heights[i] is the height of a wall column of width 1. After heavy rain, water sits on top of a column wherever there are taller columns somewhere to its left and somewhere to its right. Return a list water where water[i] is the depth of water resting on column i (0 if none).
Examples
Input: heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: [0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0]
Explanation: column 5 (height 0) is bounded by 2 on the left and 3 on the right, so it holds 2 units.
Input: heights = [3, 0, 2]
Output: [0, 2, 0]
Constraints
0 <= len(heights) <= 10**5,0 <= heights[i] <= 10**5- Target: O(n) time, O(1) extra space beyond the returned list (no prefix-max / suffix-max arrays).
Goals
- Maintain the running maximum from each side while the pointers converge
- Decide which side is safe to resolve based on which running maximum is lower