Trapping Rain Water

## Problem Given an array `height` of non-negative integers representing the elevation map where the width of each bar is 1, compute how much water it can trap after raining. ## Examples **Example 1:** ``` Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: 6 units of rain water are trapped between the bars. ``` **Example 2:** ``` Input: height = [4,2,0,3,2,5] Output: 9 ``` **Example 3:** ``` Input: height = [1,0,1] Output: 1 ``` ## Approach Hints For each index `i`, the water trapped is `min(max_left[i], max_right[i]) - height[i]`. You can precompute left and right maximums in O(n), or use a two-pointer approach to achieve O(1) space.