单调栈 Monotonic Stack

类似单调队列，区别是只在一端进行操作。

模板：最近更小值(Nearest Smaller Element)问题

CSES Nearest Smaller Values: 长度为N (\(0 \leq N \leq 10^5\))的整数数组\(a\)，对于每个位置\(i\)，请找到最大的\(j\)，使得\(j < i\)且 \(a_i > a_j\)。

这题的解法就是从左向右扫描数组，同时维护一个单调上升的栈，当新的元素大于栈顶元素时，弹出栈顶元素直到小于当前元素。这样栈顶元素就是我们要的结果。

#include <bits/stdc++.h>

using namespace std;

int N;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    stack<pair<int, int>> stack;
    stack.push({0, 0});

    for(int i = 1; i <= N; ++i) {
        int a; cin >> a;
        while(!stack.empty() && stack.top().first >= a) stack.pop();
        cout << stack.top().second << " ";
        stack.push({a, i});
    }
}

综合例题

例题：POJ 3250 Bad Hair Day，给定\(n\)头牛的身高，每头牛求它到它右边第一个比它高（或身高相等）的牛之间有多少头牛，然后将求得的结果相加就是最后的答案。

用单调栈的解法，是维护一个身高依次下降的牛的位置的栈。如果向右依次扫描时，碰到身高更低的牛就入栈。反之，则要把所有不符合顺序栈顶的牛出栈（同时也就找到了这头牛右侧第一个比它高的牛），再将当前的牛入栈。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stack>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;

int main()
{
    int i,n,top,a[80010]; //top指向栈顶元素 
    LL ans; //存储最终结果 
    stack<int> st; //st为栈，每次入栈的是每头牛的位置 
    while(~scanf("%d",&n))
    {
        while(!st.empty()) st.pop(); //清空栈 
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        a[n]=inf; //将最后一个元素设为最大值 
        ans=0;
        for(i=0;i<=n;i++) {
            if(st.empty()||a[i]<a[st.top()]) { //如果栈为空或入栈元素小于栈顶元素，则入栈 
                st.push(i);
            } else {
                while(!st.empty()&&a[i]>=a[st.top()]) { //如果栈不为空并且栈顶元素不大于入栈元素，则将栈顶元素出栈 
                    top=st.top(); //获取栈顶元素 
                    st.pop();     //栈顶元素出栈 
                    //这时候也就找到了第一个比栈顶元素大的元素 
                    //计算这之间牛的个数，为下标之差-1 
                    ans+=(i-top-1); 
                }
                st.push(i); //当所有破坏栈的单调性的元素都出栈后，将当前元素入栈 
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

习题