单调栈

单调栈（Monotonic Stack）是一种特殊的栈结构，栈中的元素保持单调递增或单调递减的顺序。它主要用于解决"下一个更大元素"、“下一个更小元素”、"前一个更大元素"等问题。

性质

1. 栈内元素保持单调性（递增或递减）
2. 新元素入栈时,破坏单调性的元素会被弹出
3. 时间复杂度通常为O(n)，因为每个元素最多入栈和出栈一次

单调栈的典型应用

• 寻找下一个更大/更小元素
• 柱状图中最大的矩形
• 接雨水问题
• 滑动窗口最大值

例如：
有n个人，每个人向右看，求她看到的第一个人

可以观察出，在这个人后面比这个人矮的是看不到的，可以将其忽略掉，可以推断出：我们看到的人肯定是一个比一个高的，而没看到的，可以直接踢出（有点残忍。。），这不就有了单调性了吗，留下来的这些人就是一个单调栈。
归纳：

1.从后往前扫
2. 对于每个点：

• 如果栈中有比它小的元素依次弹出
• 没有比它小的时，栈顶就是答案（即第一个大于它的数）
• 将这个元素存入新数组
  （由于是从前往后输出，还要把答案放到一个数组里。）

例题

（洛谷）P5788 【模板】单调栈

P5788 【模板】单调栈

题目：
给出项数为 $n$ 的整数数列 $a_{1\dots n}$。

定义函数 $f(i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的下标，即 f ( i ) = min ⁡ i < j ≤ n , a j > a i { j } f(i)=\min_{i<j\leq n, a_j > a_i} \{j\} f(i)=mini<j≤n,aj​>ai​​{j}。若不存在，则 $f(i)=0$。

试求出 $f(1\dots n)$。

输入：
第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_{1\dots n}$。
输出：
一行 $n$ 个整数表示 $f(1),f(2),\dots ,f(n)$ 的值。

输入

5
1 4 2 3 5

输出

2 5 4 5 0

说明/提示

【数据规模与约定】

对于 $30\%$ 的数据，$n\le 100$；

对于 $60\%$ 的数据，$n\le 5\times 10^3$ ；

对于 $100\%$ 的数据，$1\le n\le 3\times 10^6$，$1\le a_i\le 10^9$。

代码实现
注释很详细

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=3e6+6;
stack<int>s;
int n,a[N],f[N];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=n;i>=1;i--)//从后往前构造单调桟
	{
	while(!s.empty()&&a[s.top()]<=a[i])//当桟不空并且桟顶元素比该元素还小时
	s.pop();//出桟，维护单调的桟
	if(!s.empty())//如果桟不空，那么栈顶元素就是第一个大于该数的元素
	f[i]=s.top();//题目中要的是下标
	else
	f[i]=0;//桟空则右边没有大于该元素的数了
	s.push(i);//将每个元素的下标压入栈中
	}
	for(int i=1;i<=n;i++)//正序输出即可
	cout<<f[i]<<" ";
}
signed main()
{
	int _=1;
//	cin>>_;
	while(_--)
	solve();
	return 0;
}

（力扣）496. 下一个更大元素 I

496. 下一个更大元素 I

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=1e6+6;
void solve()
{
	vector<int>nums1,nums2;
	nums2.push_back(1);
	nums2.push_back(3);
	nums2.push_back(4);
	nums2.push_back(2);
	nums1.push_back(4);
	nums1.push_back(1);
	nums1.push_back(2);
   stack<int>s;//定义桟
   vector<int>v1;//用来存储下一个更大元素
   map<int,int>mp;//存下标和此下标值的下一个更大元素的值
   for(int i=nums2.size()-1;i>=0;i--)//从后往前构造单调桟
   {
   	while(!s.empty()&&nums2[s.top()]<=nums2[i])//桟不空并且桟中元素比此元素小
   	s.pop();//弹出桟
   	if(!s.empty())//如果桟不空
   	mp[i]=nums2[s.top()];//此下标下的值的第一个更大元素就是栈顶元素
	else
	mp[i]=-1;//若桟为空则没有更大的元素，输出-1
   	s.push(i);//将下标压入栈
   }
   for(int i=0;i<nums1.size();i++)//因为数据范围很小，可以暴力枚举
   {
   	for(auto x:mp)
   	{
   		if(nums2[x.first]==nums1[i])//找到数组1中元素在数组2中的位置
   		v1.push_back(x.second);//将这个元素的下一个更大值赋值给数组v
	}
   }
   for(auto d:v1)
   cout<<d<<" ";
   cout<<endl;
}
int main()
{
	int _=1;
//	cin>>_;
	while(_--)
	solve();
	return 0;
}

（力扣）739. 每日温度

739. 每日温度

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=1e6+6;
void solve()
{
	vector<int>a;
	a.push_back(73);
	a.push_back(74);
	a.push_back(75);
	a.push_back(71);
	a.push_back(69);
	a.push_back(72);
	a.push_back(76);
	a.push_back(73);
	stack<int>s;
	vector<int>v(a.size(),0);//初始化为0 
	int ans=0;
	for(int i=0;i<a.size();i++)//从前往后遍历 
	{
		while(!s.empty()&&a[s.top()]<a[i])//如果桟不空并且这个元素大于桟顶对应的元素，这个元素就是第一个大于桟顶元素的温度 
		{
			ans=s.top();//记录下标 
			s.pop();//弹出桟，每弹出一次就找到比弹出元素更高温的温度  
			v[ans]=i-ans;//用两下标相减记录天数差 
		}
		s.push(i);//将下标压入栈 
	}
	return v;
}
signed main()
{
	int _=1;
//	cin>>_;
	while(_--)
	solve();
	return 0;
}

84. 柱状图中最大的矩形

84. 柱状图中最大的矩形

解题思路
运用单调栈分别从前往后找左边第一个小于这个数的下标，再从后往前找右边第一个小于这个数的下标，这样就能求得满足这个高度矩形的区间长度，就能求出来在这个高度下最大的矩形面积了。

class Solution {
public:
    int largestRectangleArea(vector<int>&a) {
     int n=a.size();
	stack<int>s,st;
	int c[100005],d[100005],f[100005];
	for(int i=0;i<n;i++)
	{
		while(!s.empty()&&a[s.top()]>=a[i])
		s.pop();
		if(!s.empty())
		c[i]=i-s.top();
		else
		c[i]=i+1;
		s.push(i);
	}
	for(int i=n-1;i>=0;i--)
	{
		while(!st.empty()&&a[st.top()]>=a[i])
		st.pop();
		if(!st.empty())
		d[i]=st.top()-i;
		else
		d[i]=n-i;
		st.push(i);
	}
	int an=0;
	for(int i=0;i<n;i++)
	{
		f[i]=d[i]+c[i]-1;
		an=max(an,f[i]*a[i]);
	}
	return an;   
    }
};

P2866 Bad Hair Day S

P2866 [USACO06NOV] Bad Hair Day S
题目描述

农夫约翰有 $N$ 头奶牛正在过乱头发节。

每一头牛都站在同一排面朝右，它们被从左到右依次编号为 $1,2,\cdots ,N$。编号为 $i$ 的牛身高为 $h_i$。第 $N$ 头牛在最前面，而第 $1$ 头牛在最后面。

对于第 $i$ 头牛前面的第 $j$ 头牛，如果 $h_i>h_{i+1},h_i>h_{i+2},\cdots ,h_i>h_j$，那么认为第 $i$ 头牛可以看到第 $i+1$ 到第 $j$ 头牛。

定义 $C_i$ 为第 $i$ 头牛所能看到的牛的数量。请帮助农夫约翰求出 $C_1+C_2+\cdots +C_N$。

输入格式

输入共 $N+1$ 行。

第一行为一个整数 $N$，代表牛的个数。
接下来 $N$ 行，每行一个整数 $a_i$，分别代表第 $1,2,\cdots ,N$ 头牛的身高。

输出格式

输出共一行一个整数，代表 $C_1+C_2+\cdots +C_N$。

输入 #1

6
10
3
7
4
12
2

输出 #1

5

说明/提示

对于 $100\%$ 的数据，保证 $1\le N\le 8\times 10^4$，$1\le h_i\le 10^9$。
解题思路
要想找到每头牛能看到的所有牛的总和，只需要找到每头牛右边第一个比它高的牛的位置即可，然后将比它高的那头牛的坐标减去自己所在的下标再减1就是能看到牛的个数，因为实际上看不到比它高的那头牛，所以要减1。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=1e5+6;
int n,a[N],c[N],ans=0;
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	stack<int>s;
	for(int i=n;i>=1;i--)
	{
		while(!s.empty()&&a[s.top()]<a[i])//如果栈中的牛有比它矮的，直接踢出栈
		s.pop();
		if(!s.empty())//如果桟不空，那栈顶元素就是右边第一头比它高的牛的位置
		c[i]=s.top()-i-1;//记录下它能看到几头牛
		else//如果栈空了，说明它自己是最高的，那么在他右边的都能看到
		c[i]=n-i;//右边牛的个数
		s.push(i);//将下标入桟
	}
	for(int i=1;i<=n;i++)
	ans+=c[i];
	cout<<ans;//输出总和
}
signed main()
{
	IOS;
	int _=1;
//	cin>>_;
	while(_--)
	solve();
	return 0;
}

推荐例题：
力扣-42.接雨水
P1901 发射站