接雨水——单调栈（python）

思路利用栈的先进后出后进先出特性。使用单调栈入栈下标。当遇到更高的墙时说明形成了凹槽弹出栈元素开始计算接水量。每次弹出栈后记得要判空因为这里用的是大于要注意和求柱状图中最大矩形区别开。def rain(nums): #单调栈 stack[] #先进后出特性 res0 for i in range(len(nums)): while stack and nums[i]nums[stack[-1]]: #当遇到更高的墙说明形成了凹槽 tmpstack.pop() if not stack: #因为判断的是大于所以每弹出一次需要判断是否空 break leftstack[-1] #左边的墙 hnums[tmp] #当前高度 wi-left-1 #宽度 curHeightmin(nums[left],nums[i])-h #接水量取决于较小高度 resw*curHeight #接水量 stack.append(i) print(res) return res def main(): lineinput() numslist(map(int,line.split())) rain(nums) if __name____main__: main()