单调栈一些题目练习

最近发现单调栈不怎么会熟练使用,写点东西提醒下自己
第一题
给你一个数组$a_i$,问你对于一个长度为$i$的连续区间,最大化该区间的最小值。你需要回答长度1~n的区间的答案并且输出他们。
对于这个问题,其实我已经遇过好几次了,这类问题需要关注的是谁作为最小值而造成的区间影响.
我们认为$ai$就是当前区间的最小值,那么我们需要处理出当前该元素的最左边索引$l$,最右索引$r$,那么它就可以作为答案算入区间$r-l+1中$.
对于处理出$l,r$这两个值,这就是单调栈的作用了。
首先处理r数组,从前往后扫,如果碰到一个值$ai$大于栈顶元素,取出栈顶所有元素,把他们的值$r[j]=i$
再处理$l$数组,从后边往前边扫,如果碰到一个元素大于当前$i$,和$r$一样的处理

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
int a[maxn];int s[maxn];
int l[maxn],r[maxn],ans[maxn];
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int top = 0;
	for(int i=1;i<=n;i++){
		while(top>0&&a[s[top]]>a[i]){
			r[s[top]] =i-1;top--;
		}
		top++;
		s[top] = i;
	}
	while(top>0) r[s[top]] = n,top--;
	for(int i=n;i>=1;i--){
		while(top>0&&a[s[top]]>a[i]){
			l[s[top]] = i+1;top--;
		}
		top++;s[top]=i;
	}
	while(top>0) l[s[top]]=1,top--;
	for(int i=1;i<=n;i++){
		int len = r[i]-l[i]+1;
		ans[len] = max(ans[len],a[i]);
	}
//	for(int i=1;i<=n;i++){
//		cout<
//	}
	for(int i=n-1;i>=1;i--){
		ans[i] = max(ans[i+1],ans[i]);
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

第二题
与上题类似地,使用单调栈来分别处理第i个牛是否有那样的点x,
$x.h>2\ast a_i.h,abs(x.x-a_i.x)<=d$.
我们使用一个单调队列维护队列中的h元素单调下降性,当前元素的$h$大于队尾元素时,不断地弹出队尾.
当距离不满足要求时,不断弹出队首,这样剩下的元素就是最可能合法地与i匹配的牛,这个元素显然就是队首,因为它的h元素值最大,而且位置也符合要求,其他元素不可能比它更适合.
对于左边的情况我们正序扫描一遍,右边的情况倒序扫描一遍即可.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
struct Node{
	int x,h;
	bool operator <(const Node&rhs)const{
		return x<rhs.x;
	}
}a[maxn];
int que[maxn];
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,d;cin>>n>>d;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].h;
	sort(a+1,a+1+n);
	deque<int> dq;
	vector<bool> left(n+1,false),right(n+1,false);
	for(int i=1;i<=n;i++){
		while(!dq.empty()&&a[dq.back()].h<a[i].h) dq.pop_back();
		while(!dq.empty()&&abs(a[i].x-a[dq.front()].x)>d) dq.pop_front();
		if(!dq.empty()&&a[dq.front()].h>=2*a[i].h) left[i] = true;
		dq.push_back(i);
	}
	while(!dq.empty()) dq.pop_front();
	for(int i=n;i>=1;i--){
		while(!dq.empty()&&a[dq.back()].h<a[i].h) dq.pop_back();
		while(!dq.empty()&&abs(a[i].x-a[dq.front()].x)>d) dq.pop_front();
		if(!dq.empty()&&a[dq.front()].h>=2*a[i].h) right[i] = true;
		dq.push_back(i);
	}
//	for(int i=1;i<=n;i++){
//		cout<
//	}
//	cout<<"\n";
//	for(int i=1;i<=n;i++) cout<
//	cout<<"\n";
//	for(int i=1;i<=n;i++) cout<
//	cout<<"\n";
	int ans=0;
	for(int i=1;i<=n;i++){
		if(left[i]&&right[i]) ans++;
	}
	cout<<ans<<"\n";
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

第三题
仍然是一个比较明显的单调队列,如果我们断环为链,发现不成立的标准就是对于一个位置$i$,有$su{m}_j-su{m}_i<0(j>=i\&\&j<=i+n-1)$.那么我们发现只要选取区间$[i+1,i+n-1]中的最小的su{m}_j即可,使用单调队列维护这段最小值就能算出答案$.

#include
using namespace std;
const int maxn = 2e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];ll a[maxn],sum[maxn];
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++) a[i+n] = a[i];
	for(int i=1;i<=2*n;i++) sum[i] = sum[i-1]+a[i];
	deque<int> dq;ll ans = 0;
	for(int i=2*n;i>=1;i--){
		while(!dq.empty()&&dq.front()-i>n) dq.pop_front();
		if(i<=n&&!dq.empty()&&sum[dq.front()]-sum[i]>=0) ans++;
		while(!dq.empty()&&sum[dq.front()]>=sum[i]) dq.pop_back();
		dq.push_back(i);
	}
	cout<<ans<<"\n";
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29