# LC 42. Trapping Rain Water

### [Problem link](https://leetcode.com/problems/trapping-rain-water/)

###### tags: `leedcode` `python` `c++` `hard` `Monotone Stack` `Two Pointer`

Given <code>n</code> non-negative integers representing an elevation map where the width of each bar is <code>1</code>, compute how much water it can trap after raining.

**Example 1:**
<img src="https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png" style="width: 412px; height: 161px;" />

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:**

- <code>n == height.length</code>
- <code>1 <= n <= 2 * 10⁴</code>
- <code>0 <= height[i] <= 10⁵</code>

## Solution 1
#### Python

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left_height, right_height = [0] * n, [0] * n
        left_height[0] = height[0]
        right_height[-1] = height[-1]

        for i in range(1, n):
            left_height[i] = max(left_height[i - 1], height[i])

        for i in range(n - 2, -1, -1):
            right_height[i] = max(right_height[i + 1], height[i])

        res = 0
        for i in range(n):
            res += min(left_height[i], right_height[i]) - height[i]

        return res

#### C++

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> preMax(n);
        preMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            preMax[i] = max(preMax[i - 1], height[i]);
        }

        vector<int> sufMax(n);
        sufMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            sufMax[i] = max(sufMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int area = min(preMax[i], sufMax[i]) - height[i];
            ans += area;
        }
        return ans;
    }
};

## Solution 2 - Monotone Stack
#### Python

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        res = 0
        stack = []

        for i in range(n):
            while stack and height[i] > height[stack[-1]]:
                lower = stack.pop()
                if stack:
                    h = min(height[stack[-1]], height[i]) - height[lower]
                    w = i - stack[-1] - 1
                    res += h * w
            stack.append(i)

        return res

#### C++

class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> st;
        int res = 0;

        for (int i = 0; i < height.size(); i++) {
            while (!st.empty() && height[st.back()] < height[i]) {
                int mid = st.back();
                st.pop_back();
                if (!st.empty()) {
                    int h = min(height[st.back()], height[i]) - height[mid];
                    int w = i - st.back() - 1;
                    res += h * w;
                }
            }
            st.push_back(i);
        }
        return res;
    }
};

## Solution 3 - Two Pointer
#### C++

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left = 0;
        int right = n - 1;
        int preMax = 0;
        int sufMax = 0;
        int ans = 0;
        while (left <= right) {
            preMax = max(preMax, height[left]);
            sufMax = max(sufMax, height[right]);
            if (preMax < sufMax) {
                ans += preMax - height[left];
                left++;
            } else {
                ans += sufMax - height[right];
                right--;
            }
        }
        return ans;
    }
};

>### Complexity
>n = height.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |
>| Solution 2 | O(n) | O(n) |
>| Solution 3 | O(n) | O(1) |

## Note
sol1:
left_height: left_height[i] = max(height[:i + 1])
right_height: right_height[i] = max(height[i:])

這樣子針對每個每個位置i, 0 <= i < height.length, 低窪的地方就是min(left_height[i], right_height[i]) - 地面高度(height[i])

sol2:
維護一個大到小的stack, 遇到大於stack頂端的數字就計算可以裝水的面積
[代碼隨想錄](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0042.%E6%8E%A5%E9%9B%A8%E6%B0%B4.md)

sol3:
兩個指針紀錄左邊最大值與右邊最大值, 如果左邊最大值 < 右邊目前的最大值, 代表當前水位最多只能到左邊最大值, 反之亦然.