Description

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

Solution

1.暴力O(N^2)，实现方便

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        for i in range(1,len(height)):
            max_left = 0
            max_right = 0
            for j in range(0,i):
                if max_left < height[j]:
                    max_left =height[j]
            for j in range(i+1,len(height)):
                if max_right < height[j]:
                    max_right = height[j]
            ans += max(min(max_right,max_left)-height[i] ,0)
            
        return ans

2.使用额外的空间O(N),实现O(N)time,先从左到右遍历去max, 再从右往左遍历取max

class Solution:
    """
    @param heights: a list of integers
    @return: a integer
    """
    def trapRainWater(self, heights):
        # write your code here
        max_left =[]
        max_v = 0
        max_right = [0]*len(heights)
        for i in range(len(heights)):
            if max_v <heights[i]:
                max_v = heights[i]
            max_left.append(max_v)
        max_v = 0
        for j in range(len(heights)-1,-1,-1):
            if max_v < heights[j]:
                max_v = heights[j]
            max_right [j] = max_v
        ans = 0
        for i in range(len(heights)):
            tmp = min(max_left[i],max_right[i])
            ans += max(tmp-heights[i],0)
        return ans

3. two pointer Time O(N) Space O(1)
   注意corner case!!! 两边指针记录双向最大值，然后对比较小的那一边进行移动，计算store使用那个较短的边

class Solution:
    """
    @param heights: a list of integers
    @return: a integer
    """
    def trapRainWater(self, heights):
        # write your code here
        if len(heights) ==0:
            return 0
        left = 1
        right = len(heights)-2
        max_l = heights[0]
        max_r = heights[-1]
        ans = 0
        while left <= right:
            if max_l < heights[left]:
                max_l = heights[left]
            if max_r < heights[right]:
                max_r = heights[right]
            if max_r > max_l:
                ans += max(max_l - heights[left],0)
                left +=1
            else:
                ans += max(max_r - heights[right],0)
                right -=1
        return ans