#algo/prefix-sum # Notes - Scan left-to-right, take note of the maximum before the item (including itself). #algo/prefix-sum Denote as `prefixes`, and let $p_i$ denote the value of the $i$th prefix. - Scan right-to-left, take note of the maximum after the item (including itself). #algo/prefix-sum (postfix). Denote as `postfixes`, and let $q_i$ denote the value of the $i$th postfix. - For each item $x_i$, we define its raw value $R(x)$ as $R(x_i) := \max(p_i, q_i).$ Then, we define the raw value as: $V(x_i):=\begin{cases}R(x_i), &\text{iff}\ R(x_i) \geq 0,\\0,&\text{otherwise}.\end{cases}$ - Then, the result is $\sum V(x_i)$. # Problem ### Problem Description Given `n` non-negative integers representing an 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:** The above elevation map (black section) is represented by array `[0,1,0,2,1,0,1,3,2,1,2,1]`. In this case, `6` units of rain water (blue section) are being trapped. #### Example 2 - **Input:** `height = [4,2,0,3,2,5]` - **Output:** `9` ### Constraints - `n == height.length` - $1 <= n <= 2 * 10^4$ - `0 <= height[i] <= 10^5`