###### tags: `LeetCode` `Two Pointer` `Hard`
# LeetCode #42 [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)
### (Hard)

(Google的題目)
給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之後能接多少雨水。

---

解法1:
建立兩數組leftwall, rightwall儲存在i點時左右的牆高, 之後遍歷height計算height[i]能儲存的雨水量,為leftwall與rightwall中較低者減去height[i]。

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();      
        if(n){
            vector<int>leftwall(n,0);
            vector<int>rightwall(n,0);
            int temp=height[0];
            for(int i=0;i<height.size();i++){
                leftwall[i]=max(temp,height[i]);
                temp=max(temp,height[i]);
            }
            temp=height[n-1];
            for(int i=n-1;i>=0;i--){
                rightwall[i]=max(temp,height[i]);
                temp=max(temp,height[i]);
            }
            int ans=0;
            for(int i=0;i<n;i++){
                ans+=(min(rightwall[i],leftwall[i])-height[i]);
            }
            return ans;
        }
        return 0;
    }
};

---
解法2:
使用two pointer分別指向左右, 當左邊高度高於右邊高度時, 不須考慮左牆(因為水只會從右邊漏), 持續修正右牆高度並同時計算右牆高度減去height[right]的雨水量並進行加總直到右牆高度高於左牆, 此時換成計算左牆高度減去height[left], 如此循環直到left>right, 即可得到全部雨水數。

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