顾名思义,单调栈即栈内元素单调递增或单调递减的栈
如何维护?遍历数据
能用来干什么?在O(n)时间内为每个元素找到向右or向左起,第一个大于or小于该元素的元素下标,进行若干操作
eg1:
给定一排人及他们的高度,每个人向右看,求每个人最多能看到几个人
易知,要求每个人最多看到的人数,即求向右起第一个高于该人的位置
故用单调栈进行维护,若出栈则记录此时下标i与出栈下标top之差
eg2:
给定一系列统计图中的数据,该统计图中的最大矩形覆盖面积
易知,我们确定一个数据,向左、向右延伸直至第一个小于其大小的下标,此时计算该矩形面积,再更新最大面积
故我们可以维护两个单调栈,在O(n)内求出答案
或者只维护一个单调栈,只是要更新压入栈的数据(略抽象)