单调栈

一、单调栈简介

单调栈是一种特殊的栈，在普通栈的先进后出基础上满足单调性，从栈顶（栈底）到栈底（栈顶）单调递增或递减。递增的可以称之为单调递增栈，递减的则是单调递减栈。

举个实际的例子（单调递增栈）：

一个序列：3，5，1，9，3，找右侧第一个比当前元素小的元素。

从左往右遍历：

步数	操作	结果（右侧为栈底）	作用
1	遍历到3，此时栈为空，入栈	3	此时右侧还没有比3小的元素
2	遍历到5，此时栈顶元素为3，比5小，将5入栈	5,3	元素5大于3，继续入栈
3	遍历到1，此时1比栈顶元素5小，将5出栈，此时栈顶元素为3，再将3也出栈，将1入栈	1	找到了1，比元素5小，也比元素3小，这样元素3和元素5就找到了答案
4	遍历到9，此时9比栈顶元素1大，将9入栈。	1,9	遍历到9，比栈内元素都大，入栈
5	遍历到3，此时3比栈顶元素9小，将9出栈，此时栈顶元素为1，比3小，将3入栈	1,3	找到了3，比栈顶元素9小，元素9找到了答案，但是比元素1大，元素1没有找到答案。

遍历完整个序列后，栈内的所有元素，都是右侧没有比它还小的元素的。

二、单调栈适用的场景

单调栈主要解决下面这几种问题：

• 找右侧第一个比当前元素大的元素
• 找左侧第一个比当前元素大的元素
• 找右侧第一个比当前元素小的元素
• 找左侧第一个比当前元素小的元素

单调栈模板题：
P5788 【模板】单调栈 - 洛谷

// 主要部分代码
for (int i = 0; i < n; i++)
{
    if (st.empty() || nums[i] <= nums[st.top()]) // 栈为空或者小于栈顶元素，入栈。考虑到有相等的情况，但是题目要找大于，所以也入栈
        st.push(i);
    else
    {
        while (!st.empty() && nums[i] > nums[st.top()]) // 大于栈顶元素，要出栈，直到小于等于栈顶元素
        {
            ans[st.top()] = i + 1;
            st.pop();
        }
        st.push(i);
    }
}

记住一点：这个栈是用来记录已经遍历过，但还没有求得答案的元素的。当我们遍历元素，将得到的元素与栈内元素进行比较，如果栈内元素可以得出答案了，那一定要及时出栈，当前元素一定要入栈。

三、单调栈同时求两侧元素

上面的代码只能求得右侧比他大的第一个元素，有没有一种方法，可以同时求得左右两侧第一个比当前元素大的元素？

我们加一条限制，单调栈内的元素必须是严格单调的，即不可以出现相等的情况，然后我们分两种情况来考虑：1.没有重复元素，2.有重复元素。

1.无重复元素

举个例子：

假设此时栈内已经压入图中的元素，假设下一个元素是7，比栈顶元素3大，所以要出栈了，再出栈的同时，这个元素压着的元素就是左侧第一个比他大的，即5。

一定会是5吗？一定是的。

两种情况：

• 假设3跟5之间还有个4，那么4一定会在栈里面
• 假设3跟5之间还有个6，那么当遍历到6的时候，5会出栈，3压的是6而不是5了。

2.有重复元素

有重复元素也是跟无重复元素一样的处理方式，保证栈内是严格单调的，在记录左侧第一个最大元素时，也是记录压的那个元素，这样会有错误，但是我们最后会加以修正。

错误的地方：比如序列 1 3 3 5 第一个3按照上边的方法，右边比他大的会记录成第二个3.

最后我们加以修正，遍历一遍，看看找到的右侧第一个大于是否真的大于如果不大于，就修正为错误答案的那个元素右侧第一个最大的，比如上面的第一个3，我们会修正成第二个3的答案，即5。

可能会有疑问，那我不让他严格单调，我相等的时候直接入栈不可以吗，其实是一样的，这样做的话，右侧第一个大于是没错的，但左侧第一个大于是不对的，也是需要修正。

3.补充

其实也可以分两次求，每一次求一侧的，这样考虑的东西也少，时间复杂度也都是O(n)。