Trapping Rain Water

You are given an array heights of non-negative integers, where each element represents the height of a vertical bar placed on flat ground at that index. All bars have a uniform width of 1 unit and are lined up side by side with no gaps.

Imagine it starts raining. Water falls onto this skyline and any water that lands on top of the bars will settle into the low spots between them, held in place by the taller bars on either side, until it either overflows past the shorter of the two surrounding walls or has nowhere to go. Water resting exactly on top of a bar (not above it) does not count.

Your task is to compute the total volume of water that remains trapped across the whole array after the rain has fallen and settled, measured in the same square-unit terms as the bar heights (width 1 per column).

• Water above a given column can only be trapped up to the height of min(tallest bar to its left, tallest bar to its right), minus the height of the column itself (never negative).
• The two outermost columns can never trap any water, since there is nothing to hold water in on one side.
• Return a single integer: the total trapped water.

Examples

Example 1:

Input: heights = [3,0,2,0,4]

Output: 7

Explanation:

• At index 1 (height 0): bounded by 3 on the left and 4 on the right, so it can hold min(3,4) - 0 = 3 units.
• At index 2 (height 2): bounded by 3 and 4, so it holds min(3,4) - 2 = 1 unit.
• At index 3 (height 0): bounded by 3 (via index 2's max-left of 3) and 4, so it holds min(3,4) - 0 = 3 units.
• Total: 3 + 1 + 3 = 7.

Example 2:

Input: heights = [5,5,5,5]

Output: 0

Explanation:

All bars are the same height with no dip between them, so there is no basin for water to collect in — the answer is 0.

Example 3:

Input: heights = [4,1,3,1,5,2]

Output: 8

Explanation:

• Index 1 (height 1): bounded by 4 and 5, holds min(4,5) - 1 = 3.
• Index 2 (height 3): bounded by 4 and 5, holds min(4,5) - 3 = 1.
• Index 3 (height 1): bounded by 4 and 5, holds min(4,5) - 1 = 3.
• Index 5 (height 2): bounded by 5 on the left and nothing taller on the right, so it holds 0 (it's an edge, water would spill off the end).
• Total: 3 + 1 + 3 + 0 = 8.

Constraints

• 1 <= heights.length <= 2 * 10^4
• 0 <= heights[i] <= 10^5
• The array represents a fixed, immovable terrain profile; you must consider the full array in one pass or computation.
• The answer is guaranteed to fit in a 32-bit signed integer.