###### tags: `Leetcode` `hard` `pointer` `array` `python` `Top 100 Liked Questions`

# 42. Trapping Rain Water

## [題目來源:] https://leetcode.com/problems/trapping-rain-water/

## 題目:
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.

###### [圖片來源:]https://leetcode.com/problems/trapping-rain-water/

## 解題想法:
* 法1: 考慮每個位置pox可以增加的容量
* 取pos左邊最高與po右邊最高位置
* 兩者取較小的
* 最終減去pos本身，即為該pos可增加的容量
1. 從左向右，求每個位置的左邊最高位置
2. 從右向左，求每個位置的右邊最高位置
3. 最終再遍歷，累加每點的容量

## Python (法1: O(n) ):

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0
        n=len(height)
        res=0 
        left_max=[0]*(n)
        right_max=[0]*(n)
        
        #求左邊最大 從左->右遍歷
        left_max[0]=height[0] #最左邊設為初始
        for i in range(1,n):
            #每次比較前一個left_max與當下自己的值
            left_max[i]=max(left_max[i-1],height[i])
        #求右邊最大 從右->左遍歷
        right_max[-1]=height[-1] #最右邊設為初始
        for i in range(n-2,-1,-1):
            right_max[i]=max(right_max[i+1],height[i])
        #求每點可增加值 並累加
        for i in range(n):
            res+=min(left_max[i],right_max[i])-height[i]
            
        return res
        
result=Solution()
ans=result.trap(height = [0,1,0,2,1,0,1,3,2,1,2,1])
print(ans)

* 法2: 使用兩個pointer，head、tail分別指向左右兩端，再設兩個left_max、right_max紀錄左右邊目前最大值
* 每次比較height[head]、height[tail]大小
* if height[head]<height[tail]，表示左邊小
* 則再比較height[head]與left_max
* 若left_max>height[head]，表示其差值為height[head]可以增加的容量
* 若left_max<height[head]，則left_max換人當

## Python (法2: O(n) ):

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0
        head=0
        tail=len(height)-1
        left_max=0  #記錄左邊最大
        right_max=0 #記錄右邊最大
        res=0
        
        while head<tail:
            if height[head]<height[tail]: #左邊小
                if height[head]<left_max:
                    res+=left_max-height[head]
                else:
                    left_max=height[head]
                head+=1
            else: #右邊小
                if height[tail]<right_max:
                    res+=right_max-height[tail]
                else:
                    right_max=height[tail]
                tail-=1
        return res

result=Solution()
ans=result.trap(height = [0,1,0,2,1,0,1,3,2,1,2,1])
print(ans)