Crates of width 1 stand side by side; heights[i] is the height of stack i. After a storm, water collects wherever it is enclosed on both sides by taller stacks and runs off the two ends. Return the total number of unit squares of water held.
Examples
Input: heights = [3, 0, 2, 0, 4]
Output: 7
Explanation: Above the columns: 3, 1, 3 units (the walls 3 and 4 hold water up to level 3).
Input: heights = [2, 1, 2]
Output: 1
Constraints
0 <= len(heights) <= 10**5,0 <= heights[i] <= 10**5.- Target complexity: O(n) time, O(1) extra space.
Goals
- Express the water above a column through the tallest walls on both sides
- Replace the two prefix-maximum arrays with two pointers
- Reach O(n) time and O(1) extra space