接雨水——单调栈（python）

思路：利用栈的先进后出，后进先出特性。

使用单调栈，入栈下标。当遇到更高的墙时，说明形成了凹槽，弹出栈元素，开始计算接水量。每次弹出栈后，记得要判空，因为这里用的是大于，要注意和求柱状图中最大矩形区别开。

def rain(nums): #单调栈 stack=[] #先进后出特性 res=0 for i in range(len(nums)): while stack and nums[i]>nums[stack[-1]]: #当遇到更高的墙，说明形成了凹槽 tmp=stack.pop() if not stack: #因为判断的是大于，所以每弹出一次，需要判断是否空 break left=stack[-1] #左边的墙 h=nums[tmp] #当前高度 w=i-left-1 #宽度 curHeight=min(nums[left],nums[i])-h #接水量取决于较小高度 res+=w*curHeight #接水量 stack.append(i) print(res) return res def main(): line=input() nums=list(map(int,line.split())) rain(nums) if __name__=="__main__": main()