青年节快乐！

单调栈&单调队列

1.单调栈

  • 1.从栈底到栈顶满足单调性的结构。
  • 2.“栈+维护单调性”
  • 3.单调栈作用：把序列中每个元素放到单调栈中维护就可以快速求出区间每个元素的最大/最小值。
  • 性质：元素入栈之前会把栈顶破坏单调性的元素删除，保证元素入栈后栈仍保持单调性。
  • 一般使用单调栈的题目具有以下两点：离自己最近（栈的后进先出性质），比自己大/小/高/低.

其实单调队列相关问题（尤其是单调队列DP）可以用RMQ来解。本质就是以更加优秀的复杂度求区间最大最小值（甚至RMQ还可以求更多满足条件的值）

经验之谈：不要用 stackstack 会被卡卡卡卡常。。。

1.奶牛排队

  • very easy板子走起
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
stack <int> s;
int n, x;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		while (!s.empty() and s.top() >= x) s.pop();
		printf("%d ", (s.empty() ? 0 : s.top()));
		s.push(x);
	}
}

2.B. 牛的视野

  • 板子变异了，需要再加一步计算的公式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
stack <long long> s;
long long n, x, ans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		while (!s.empty() and s.top() <= x) s.pop();
		ans += s.size();
		s.push(x);
	}
	printf("%d\n",ans);
}

C.滑动窗口

image

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
deque <int> q;
int a[N],n,k;

int main(){
	cin>>n>>k;
	for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
	for(int i = 1;i <= n;i++){
		if(!q.empty() and q.front() < i-k+1) q.pop_front();
		while(!q.empty() and a[q.back()] >= a[i]){
			q.pop_back();
		}
		q.push_back(i);
		if(i >= k) printf("%d ",a[q.front()]);//满k个数
	}
	puts("");
	q.clear();
	for(int i = 1;i <= n;i++){
		if(!q.empty() and q.front() < i-k+1) q.pop_front();
		while(!q.empty() and a[q.back()] <= a[i]){
			q.pop_back();
		}
		q.push_back(i);
		if(i >= k) printf("%d ",a[q.front()]);//满k个数
	}
}

[单调栈]D.最大长方形

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
/*
单调队列经典中的经典。
我们遍历每个柱，设当前广告牌的高度就是当前柱的高度。
看左面和右面有多少个大于等于它的柱，就能得出广告牌的宽。
最终广告牌的大小就是该柱的高度*宽。遍历每个取最大即可。
那么左面的柱的数量就是第一个它的位置-高度小于它的位置，右面同理。
*/
#include <bits/stdc++.h>
using namespace std;
long long st[1010100], t; //存储下标，方便计算宽度。
long long a[1010100], n;
long long loww[1010100], hi[1010100];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		while (t != 0 and a[st[t]] >= a[i]) t--;
		loww[i] = i - st[t];
		st[++t] = i;
		
	}t = 0;
	st[0] = n + 1; //Why not n?
	for (int i = n; i >= 1; i--) {
		while (t != 0 and a[st[t]] >= a[i]) t--;
		hi[i] = st[t] - i;
		st[++t] = i;
	}

	long long maxx = 0;
	for (int i = 1; i <= n; i++) {
//		cout << a[i] << " " << loww[i] << " " << hi[i] << endl;
		maxx = max(maxx, a[i] * (hi[i] + loww[i] - 1/*Why?*/));
	}
	cout << maxx << endl;
}

E.最大和

  • 这里笔者使用单调队列优化区间DP
  • dpidp_i 为以 ii 结尾长度为 1∼m1\sim m 之间的数的和的最大值。
  • sis_i 是前缀和。

dpi=max{si−sj}⇔dpi=si−min{sj}(j∈[i−m∼i−1])dp_i = max\{s_i-s_j\} \Leftrightarrow dp_i=s_i-min\{s_j\} (j\in [i-m\sim i-1]) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10,L = 20;
int s[N],q[N],h,t,n,m,x;

int main(){
	cin>>n>>m;
	for(int i = 1;i <= n;i++){
		cin>>x;
		s[i] = s[i-1]+x;
	}
	int ans = -0x3f3f3f3f;
	for(int i = 1;i <= n;i++){
		if(q[h] < i-m) h++;
		while(h <= t and s[i] <= s[q[t]]) t--;
		ans = max(ans,s[i]-s[q[h]]);
		q[++t] = i;
	}
	cout<<ans<<endl;
}