单调栈 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;
}

习题

习题
CSES1142	CSES	Advertisement		普及+/提高	解答
P3668	USACO Gold	Modern Art 2	2017	提高+/省选-	解答