题目描述：
题目描述
思路分析
本题思路与之前的84,239题目一样采用单调栈（队列）的具体的思路可以参见 :
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
def calculateRainFall(m,n,h):
res = 0
for i in range(m+1,n):
res+= h-height[i]
return res
def top(s):
return s[-1] if len(s)>0 else (999999,0)
stack =[]
rainFall = 0
for idx, e in enumerate(height):
if len(stack)==0 or top(stack)<e:
stack.append((e,idx))
else:
while(top(stack)[0]<e):
hi,sn = stack.pop()
if len(stack)==0 and (idx-sn>1): #如果遇到栈顶
# here 计算入栈雨量
rainFall+=calculateRainFall(sn,idx,hi)
stack.append((e,idx))
# 2. 开始弹栈
hit,snt = 0,0
while (len(stack)>1):
hi,sn = stack.pop()
hit,snt =top(stack)
# 计算出栈雨量
if (sn-snt>1):
rainFall += calculateRainFall(snt,sn,hi)
return rainFall
结论复杂度分析
本题当中数字进栈一次出栈一次 ，所以最终的复杂度为O（2N）
