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]))

全部评论

相关推荐

06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
水墨不写bug:疑似没有上过大学
点赞 评论 收藏
分享
哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务