浅谈单调栈

单调栈，顾名思义，具有单调性的栈。

• 单调，指满足一个序列是一个从小到大的序列或从大到小的序列。

• 栈（\(stack\)）是以一种线性存储结构，它具有以下特点：栈中的数据元素遵守“先进后出（\(First\ in\ Last\ out\)）”的原则，简称 FILO 结构；限定只能在栈顶进行插入和删除操作。

所以，何为单调栈，我们只需要维护一个具有单调性的栈。

如何维护一个具有单调性的栈，我们以单调递增栈为例。

• 将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

• 我们来模拟一下单调栈的过程。

• 例如，现在栈中自底向顶的序列为 \(\{0,2,5,10,32\}\)。

  • 现在，我们需要将 \(3\) 加入栈中。
    • 我们比较 \(0\) 和 \(3\) 的大小，发现 \(0<3\)，所以将 \(0\) 弹出栈。
    • 我们接着比较 \(2\) 和 \(3\) 的大小，发现 \(2<3\)，所以将 \(2\) 弹出栈。
    • 我们接着比较 \(5\) 和 \(3\) 的大小，发现 \(5>3\)，所以 \(3\) 进入栈。比较结束。
    • 此时栈中自底向顶的序列为 \(\{3,5,10,32\}\)。
  • 接着，我们需要将 \(20\) 加入栈中。
    • 我们比较 \(20\) 和 \(3\) 的大小，发现 \(3<20\)，所以将 \(3\) 弹出栈。
    • 我们接着比较 \(20\) 和 \(5\) 的大小，发现 \(5<20\)，所以将 \(5\) 弹出栈。
    • 我们接着比较 \(20\) 和 \(32\) 的大小，发现 \(32>20\)，所以 \(20\) 进入栈。比较结束。
    • 此时栈中自底向顶的序列为 \(\{20,32\}\)。
  • 接着，我们需要将 \(50\) 加入栈中。
    • 我们比较 \(50\) 和 \(32\) 的大小，发现 \(50>32\)，所以将 \(32\) 弹出栈。
    • 此时，栈为空，所以 \(50\) 进入栈。

所以，我们用伪代码描述如下：

insert x
while !sta.empty() && sta.top()<x
    sta.pop()
sta.push(x)
//by oi-wiki.org

接下来，讲几道比较经典的题：

• HISTOGRA - Largest Rectangle in a Histogram
  • 如果是递增的我们就放着不管，以后来处理。如果说下一个高度更小，那么用它所构成的矩形的高度不可能超过它自己，而后面的矩形想要和前面的矩形拼接的话，高度也不能超过它。
  • 这样子的话，我们可以用上面的方法更新比当前矩形高的矩形的答案再将它们合并。
  • 我们可以借助单调性处理问题的思想在于及时排除不可能的选项，保持策略集合的高度有效性和秩序性。
  • 我们从左到右读入矩形，如果当前矩形比栈顶矩形高，即满足单调递增，进栈。否则不断去除栈顶，直至栈空或栈顶高度低于当前矩形。在此过程中，我们累计被弹出的矩形的宽度和（用于计算答案与合并），用 \(高度\times累计宽度\) 更新答案。而后，将一个宽度为累计宽度，高度为当前矩形的矩形入栈。结束，将剩余矩形弹出，和上面一样更新答案；

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e7+5;
ll a[MAXN],ans;
int j;
stack<int> s;
inline ll read(){
    int x=0,f=1;
    ll ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
    int n=read();
    for(int i=0;i<n;++i){
    	a[i]=read();
	} 
    while (j<=n){
        if (s.empty() || a[s.top()]<=a[j]){
        	s.push(j++);
		}
    	else{
            ll temp=s.top(),wide;
			s.pop();
			if (s.empty()) wide=j;
			else wide=(j-s.top()-1);
            ans=max(ans,a[temp]*wide);
        }
    }
    printf("%lld\n",ans);
}
//by sjh

• [BZOJ1657][Usaco2006 Mar] Mooo 奶牛的歌声
  • 比较基础的单调栈题。
  • 从前往后跑一遍，再从后往前跑一遍。
  • 取 \(\max {\textstyle \sum_{i=1}^{n}} f[i]\) 即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e4+5;
struct node{
	int h,v;
}p[MAXN];
int f[MAXN];
stack<pair<int,int> > s;
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d %d",&p[i].h,&p[i].v);
	}	
	for(int i=1;i<=n;++i){
		if (!s.size()) s.push({p[i].h,p[i].v});
		else{
			while (!s.empty()){
				pair<int,int> t=s.top();
				if (t.first<p[i].h){
					s.pop();
					f[i]+=t.second;
				}
				else break;
			}
			s.push({p[i].h,p[i].v});
		}
	}
	while (!s.empty()){
		s.pop();
	}
	for(int i=n;i>=1;--i){
		if (!s.size()) s.push({p[i].h,p[i].v});
		else{
			while (!s.empty()){
				pair<int,int> t=s.top();
				if (t.first<p[i].h){
					s.pop();
					f[i]+=t.second;
				}
				else break;
			}
			s.push({p[i].h,p[i].v});
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}