Standard Bar Stack and Queues · Monotonic Stack and Queue O(n) · O(1)
A solar farm installs panels of varying heights in a single row. When a storm passes, water pools in the valleys between taller panels — every position holds water up to the level of the shorter wall on its sides. The auditor walks the row once, computing exactly how many units of water the layout retains.
Input: A non-negative integer array height where height[i] is the elevation of position i.
Output: Return the total units of trapped water.
1 <= height.length <= 2 * 10^40 <= height[i] <= 10^5Input: {"height":[0,1,0,2,1,0,1,3,2,1,2,1]}
Output: 6
Valleys at indices 2, 4-6, 9 hold units bounded by the surrounding tall panels, totalling 6.
Input: {"height":[4,2,0,3,2,5]}
Output: 9
The deepest pools sit over the low ground between the 4 and the 5.