标签:单调栈

OI

[POJ2559]Largest Rectangle in a Histogram[单调栈]

cgazn阅读(93)评论(0)赞(0)

题面 假如前面一段矩形高度是递增的, 现在来一个矮的矩形, 前面高出的那一截由于这个矮矩形对后面就没有贡献了, 我们只需要知道它们的宽度. 所以可以建立一个高度单调递增的单调栈, 如果新进来的矩形不满足单调, 就把比它高的矩形都弹出, 弹出...