# [LeetCode 42. Trapping Rain Water ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/612/week-5-july-29th-july-31st/3833/)
### Daily challenge Jul 31, 2021 (HARD)

>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.


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

:::info
**Example 2:**
**Input:** height = [4,2,0,3,2,5]
**Output:** 9
:::

:::warning
**Constraints:**
* n == height.length
* 0 <= n <= 3 * 104
* 0 <= height[i] <= 105
:::

---

### Approach 1 : Two Pointer :bulb:
**`4 ms ( 89.31% )`** **`O(N)`**

* **`max_left_h`**、**`max_right_h `** 紀錄兩邊當前最大的高度。
* 判斷條件 :
>1. **`height[left] >= height[right]`** ---> 左邊較高。
>> 表示需要移動 `right` ---> 先計算 `right` 當前可以留住多少雨。
>>* `ans += max_right_h - height[right]`。
>>* `right` 左移。
>2. **`height[left] < height[right]`** ---> 右邊較高。
>> 與 `1.` 相反。

:::success
為什麼可以直接計算 **`ans += max_right_h - height[right]`**？
因為 `left` 比 `right` 還要大，就表示目前 `left` 也比 `max_right_h` 還要大，所以一定可以留住的雨量為 `max_right_h - height[right]`。
:::

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

### Approach 2 : Stack :book:
**`4 ms ( 89.31% )`** **`O(N)`**

* **`Stack<int> s`** 紀錄 `index`。
* `current` 從 `0` 開始遍歷。
> * `height[current] > height[s.top()]` ---> 有機會留住雨。
>> 1. **`middle_index = s.top()`**
>> **`s.pop()`**
>> ---> `middle_index` 被 `current` 跟 `s.top()` 所包夾。
>> ---> 若此時 `s` 為空，表示左邊高度都小於 `height[middle_index]`，無法留住雨。
>> 2. **`dif = current - s.top() - 1`** 表示 `current` 與 `s.top()` 之間的距離。
>>
>> **`h = min(height[current], height[s.top()]) - height[middle_index]`** 表示 `current`、`middle_index`、`s.top()` 三者可以形成的最高留雨高度。
>>
>> **`ans += dif * h`** 表示可留住的雨量。
>* 將 `height[current]` 放入 `s`。

---
:::success

**`dif = 1`**、**`h = min(3, 2) - 0 = 2`**。
**`ans = dif * h = 2`**。

:::

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, current = 0;
        stack<int> s;   // store index
        
        while(current < height.size()){
            while(!s.empty() && height[current] > height[s.top()]){
                int middle_index = s.top();
                s.pop();
                    
                if(!s.empty()){
                    int dif = current - s.top() - 1;
                    int h = min(height[current], height[s.top()]) - height[middle_index];
                    ans += dif * h; 
                }
            }
            s.push(current++);
        }
        
        return ans;
    }
};