单调栈与单调队列复习笔记

简介

有时候，我们让 栈/队列 中的所有元素满足单调，然后处理会比较方便。

P2947 [USACO09MAR]Look Up S

给出一个长度为 \(N\) 的序列 \(A\)，求出一个序列 \(P\)，使得 \(P_i\) 为最大的 \(j\)，使得 \(j<i\) 且 \(A_j>A_i\)（若不存在，则 \(P_i=0\)）。输出 \(P\)。\(1 \leq N \leq 10^6\)。

首先显然存在 \(O(N^2)\) 暴力，可以拿到 \(92\) 分。然后考虑优化：

维护一个单调递增栈 \(S\)，存储位置，将不满足递增性质（即，\(\forall i,j(i<j) A_{S_i} <A_{S_j}\) ）的多余元素出栈，然后不难发现，栈顶就是答案。注意，如果是栈为空，那么答案是 \(0\)。

时间复杂度 \(O(N)\)。

参考代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

stack<int> sta;
int n,h[1000005];
int ret[1000005];

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=n;i;i--){
		while(!sta.empty()&&h[sta.top()]<=h[i]){
			sta.pop();
		}
		ret[i]=((sta.empty())?0:sta.top());
		sta.push(i);
	}
	for(int i=1;i<=n;i++){
		cout<<ret[i]<<'\n';
	}
	return 0;
}

P2866 [USACO06NOV]Bad Hair Day S

给出一个长度为 \(N\) 的序列 \(h\)，你需要求出一个序列 \(C\) 使得 \(C_i\) 为所有满足 \(j<i\) 且 \(h_j>h_i\) 的 \(j\) 的个数。求 \(\sum\limits_{i=1}^{n}{C_i}\)。\(1 \leq N \leq 80000\)。

感觉这两道题的唯一区别就是一个求最近的，一个求总数。不难发现，\(C_i\) 就是求当前单调栈的大小。

时间复杂度 \(O(N)\)。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

stack<int> sta;
int n,h[1000005];
int ret;

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=1;i<=n;i++){
		while(!sta.empty() && h[sta.top()]<=h[i]){
			sta.pop();
		}
		if(!sta.empty())ret+=sta.size();
		sta.push(i);
	}
	cout<<ret;
	return 0;
}

P3467 [POI2008]PLA-Postering

原文地址：http://www.cnblogs.com/zheyuanxie/p/monotonous-data-structures.html