leetcode 42 接雨水

暴力解法，每次根据当前值去寻找左右两边的最高值，然后根据min()的值减去当前值来计算当前位置能接多少雨水。
时间O(n^2)，会超时。

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

        return sumval

通过数组换时间，使用动态规划方法，避免每次都循环寻找左边和右边的最大值，每次将左边最大值与右边最大值与前一个元素的左右最大值比较，这样通过一次遍历就可以求出所有元素的左右最大值，然后根据一次循环求得面积。

class Solution:
    def trap(self, height: List[int]) -> int:
        sumval=0
        max_left=[0 for _ in range(len(height)+1)]
        max_right=[0 for _ in range(len(height)+1)]
        max_left[0]=0
        max_left[len(height)-1]=0
        for i in range(1,len(height)+1):


            max_left[i]=max(max_left[i-1],height[i-1])
        for j in range(len(height)-2,-1,-1):   
            max_right[j]=max(max_right[j+1],height[j+1])
        for i in range(len(height)):
            if min(max_left[i],max_right[i])-height[i]>0:
                sumval+=min(max_left[i],max_right[i])-height[i]
            #print(sumval)

        return sumval

数组会占用空间，所以考虑双指针是否可以解决问题，左右两个指针，左右指针指的数字哪边小，证明这边坑里面的水不会露出，所以就计算这边的高度差，left+=1,当右边的值大于左边的值的时候，就计算右边的高度差,right+=1，类似快速排序。主要是选择左右值更小的一方算坑里面的值，因为更小一边一定不会露出。

class Solution:
    def trap(self, height: List[int]) -> int:
        if height==[]:
            return 0
        left=0
        right=len(height)-1
        max_left=height[left]
        max_right=height[right]
        sumval=0

        while left<=right:

            if max_left<=max_right:
                if max_left>height[left]:
                    sumval+=max_left-height[left]
                left+=1

                if  left<len(height) and height[left]>max_left :
                    max_left=height[left]

            else:
                if max_right>height[right]:
                    sumval+=max_right-height[right]
                right-=1
                if  right>=0 and height[right]>max_right :
                    max_right=height[right]

        return sumval

按照行来求面积，按照第一行，第二行求面积，然后再减去柱体面积的和。

class Solution:
    def trap(self, height: List[int]) -> int:
        left=0
        right=len(height)-1
        temp=1
        sumval=0
        while left<=right and temp <=max(height):
            while height[left]<temp:
                left+=1
            while height[right]<temp:
                right-=1
            sumval+=right-left+1
            temp+=1
        return sumval-sum(height)

从左到右，从右到左，按照当前的最高高度求面积，然后发现多加一个的矩形的面积，减去。

class Solution:
    def trap(self, height: List[int]) -> int:
        if height==[]:
            return 0
        left=0
        right=len(height)-1
        max_left=height[left]
        max_right=height[right]
        sumval=0
        while left<len(height) and right>=0:
            max_left=max(height[left],max_left)
            max_right=max(height[right],max_right)
            sumval+=max_left+max_right
            left+=1
            right-=1
        return sumval-sum(height)-len(height)*max_left

单调栈，单调元素入栈，当栈不为空且栈顶元素比入栈元素小时，也就是遇到转折点时，出栈元素开始循环计算当前出栈元素位置的水量。如果空栈就break,等待入栈元素。

class Solution:
    def trap(self, height: List[int]) -> int:
        stack=[]
        idx=0
        res=0
        while idx<len(height):
            while stack and height[idx]>height[stack[-1]]:
                s=stack[-1]
                stack=stack[:-1]
                if not stack:
                    break
                res+=(min(height[stack[-1]],height[idx])-height[s])*(idx-stack[-1]-1)
            stack.append(idx)
            idx+=1
        return res