【接雨水】python刷题记录

R4-栈与队列篇

目录

方法1：前后缀分解

方法2：双指针法（优化了空间）

方法3：单调栈 

和之前的一道题有些类似

【盛最多水的容器】python刷题记录

思路：

方法1：前后缀分解

走到i个位置时，min(前缀和与本次h相比的最大值，后缀和与本次h相比的最大值）- i个位置的高度

class Solution:
    def trap(self, height: List[int]) -> int:
        n=len(height)
        #前缀和数组
        pre=[0]*n
        pre[0]=height[0]
        for i in range(1,n):
            pre[i]=max(pre[i-1],height[i])
        #后缀和数组
        last=[0]*n
        last[-1]=height[-1]
        for i in range(n-2,-1,-1):
            last[i]=max(last[i+1],height[i])
        #计算
        ret=0
        for h,pre_i,last_i in zip(height,pre,last):
             ret+=min(pre_i,last_i)-h
        return ret

方法2：双指针法（优化了空间）

注意 while 循环可以不加等号，因为在「谁小移动谁」的规则下，相遇的位置一定是最高的柱子，这个柱子是无法接水的。

class Solution:
    def trap(self, height: List[int]) -> int:
        n=len(height)
        pre_max=0
        last_max=0
        ret=0
        left=0
        right=n-1
        while left
            pre_max=max(pre_max,height[left])
            last_max=max(last_max,height[right])
            if pre_max<=last_max:
                ret+=pre_max-height[left]
                left+=1
            else:
                ret+=last_max-height[right]
                right-=1
        return ret

方法3：单调栈 

前两种方法都是横向接水

单调栈能够实现纵向接水

class Solution:
    def trap(self, height: List[int]) -> int:
        #栈
        st=[]
        ret=0
        for i,h in enumerate(height):
            while st and h>=height[st[-1]]:
                #决定面积的3个点，栈顶，当前不满足单调栈的点，次栈顶
                ding_st=height[st.pop()]
                #此时栈空
                if not st:
                    break
                ci_st=st[-1]
                ret+=(min(height[ci_st],h)-ding_st)*(i-ci_st-1)
            st.append(i)
        return ret