单调栈的特性:本质上是一个stack,但是加入了额外约束。即栈内元素是单调有序的。
为了保持单调性,需要改写push函数,以单调递增栈为例(从bottom到top递增),那么push元素进栈的时候,先过一个while循环,依次比较栈顶元素与新元素的大小,新元素大于栈顶的话,则pop,直到stack为空,或者找到第一个大于新元素的做栈顶。
由于这样的push删除了很多信息,因此,只有在这些信息对于后续的使用没有价值,不影响后续判断的任务下,才可以使用单调栈。
常见的几种任务场景:
数组中某个元素后面位置里比它大的元素值。(next greater number类)
variants:求next greater number与当前元素的位置关系(只需将比较value改成比较arr[i]然后存储i即可)。