数据结构-单调栈

😊 | Powered By HeartFireY | 单调栈(参考自OIWIKI) 📕 | 需要的前导知识：栈 一、单调栈简介

单调栈即为满足单调性的栈结构。与栈相似，只允许在一端进行进出操作。

单调栈可以用于寻找下一个最大数，也可寻找下一个最小数，以及建立在这基础上的更高级的模型。

二、单调栈的结构与操作 1.插入操作

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

例如，栈中自顶向下的元素为 1 , 3 , 5 , 10 , 30 , 50 {1,3,5,10,30,50} 1,3,5,10,30,50，插入元素 20 20 20 时为了保证单调性需要依次弹出元素 1 , 3 , 5 , 10 1,3,5,10 1,3,5,10，操作后栈变为 20 , 30 , 50 20,30,50 20,30,50。

用伪代码描述如下：

insert x
while !sta.empty() && sta.top()