# 0042. Trapping Rain Water
###### tags: `Leetcode` `Hard` `FaceBook` `Bloomberg`
Link: https://leetcode.com/problems/trapping-rain-water/
## 思路
先找到global maximum，然后从左边开始遍历，一直到遍历到global maximum，记录currMax,每次 ans = ans+ (currMax-currHeight)，然后再从右边开始遍历，道理一样
## Code

class Solution {
    public int trap(int[] height) {
        int maxHeight = 0;
        int lastIdx = 0;
        for(int i = 0;i < height.length;i++){
            if(height[i]>=maxHeight){
                maxHeight = height[i];
                lastIdx = i;
            }
        }
        
        int currMax = 0;
        int ans = 0;
        for(int i = 0;i < lastIdx;i++){
            if(currMax<height[i]){
                currMax = height[i];
            }
            else{
                ans += currMax-height[i];
            }
        }
        currMax = 0;
        for(int i = height.length-1;i > lastIdx;i--){
            if(currMax<height[i]){
                currMax = height[i];
            }
            else{
                ans += currMax-height[i];
            }
        }
        return ans;
    }
}