单调栈

分类：

单调栈也分为单调递增栈和单调递减栈

• 单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小
• 单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大

举例：单调递增栈

现在有一组数10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。

10入栈时，栈为空，直接入栈，栈内元素为10。

3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。

7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。

4入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。

12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。

伪代码

stack<int> st;
//单调递增栈
for (遍历这个数组)
{
	if (栈空 || 栈顶元素大于等于当前比较元素)
	{
		入栈;
	}
	else
	{
		while (栈不为空 && 栈顶元素小于当前元素)
		{
			栈顶元素出栈;
			更新结果;
		}
		当前数据入栈;
	}
}

应用：

主要用于$O(n)$ 解决NGE问题（Next Greater Element）

• 比当前元素更大的下一个元素
• 比当前元素更大的前一个元素
• 比当前元素更小的下一个元素
• 比当前元素更小的前一个元素

参考

https://blog.csdn.net/lucky52529/article/details/89155694