day 48 | 单调栈

接雨水和*********两道题

接雨水

• 维持一个单调递减的list，如果有一个高出的元素且当前 list 有至少两个元素，那么我们就可以找到一部分是可以装水的。装完之后则可以pop 出去维持单调性

if len(stack)>=2:
  h = min(stack[-2][1],height[i])-stack[-1][1]
  w=i-stack[-2][0]-1
  count+=w*h

柱状图最大矩形

• 题目可以翻译为在一维数组中对每一个数找到一个比自己小的元素，这样构成的矩形面积可以看做这个数构成的最大矩形

while stack and heights[i]<stack[-1][1]:
  if len(stack)>=2:
	h = stack[-1][1]
	w = i-stack[-2][0]-1
	res = max(res,h*w)
  stack.pop()
stack.append((i,heights[i]))