【单调栈】AcWing 131. 直方图中最大的矩形
2021-07-21 12:27:00 # ACM

题链

单调栈非常好的讲解

简单易懂

利用单调栈：寻找比$p[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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h> 
using namespace std;
#define ll long long 
#define LL long long 
#define MS 3000009

LL n,m;
stack<LL > sta;
LL ans;
struct node{
	int l,r;
	LL val;
}p[MS];

void solve(){
	p[n+1] = p[0] = {0,0,-1};
	for(int i=1;i<=n+1;i++){ // 寻找 p[i] 后第一个比 p[i] 小的位置 
		if(sta.empty() || p[sta.top()].val <= p[i].val) sta.push(i);
		else{
			while(!sta.empty() && p[sta.top()].val > p[i].val){
				int t = sta.top();
				sta.pop();
				p[t].r = i-1;
			}
			sta.push(i);
		}
	}
	while(!sta.empty()) sta.pop();
	for(int i=n;i>=0;i--){ // 寻找 p[i] 前第一个比 p[i] 小的位置 
		if(sta.empty() || p[sta.top()].val <= p[i].val) sta.push(i);
		else{
			while(!sta.empty() && p[sta.top()].val > p[i].val){
				int t = sta.top();
				sta.pop();
				p[t].l = i+1;
			}
			sta.push(i);
		}
	}
	while(!sta.empty()) sta.pop();
	// getans 
	LL ans = 0;
	for(int i=1;i<=n;i++){
		ans = max(ans ,p[i].val*(p[i].r-p[i].l+1));
	}
	cout << ans << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	while(cin >> n && n){
		for(int i=1;i<=n;i++){
			cin >> p[i].val;
			p[i].l = p[i].r = i;
		}
		solve();
		
	}
	

	return 0;
}

小小优化

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
#include<bits/stdc++.h> 
using namespace std;
#define ll long long 
#define LL long long 
#define MS 3000009

LL n,m;
LL p[MS];
stack<LL > sta;
LL ans;

void solve(){
	ans = 0;
	p[++n] = -1;
	for(int i=1;i<=n;i++){
		if(sta.empty() || p[sta.top()] <= p[i]){
			sta.push(i);
		}
		else{
			LL t;
			while(!sta.empty() && p[sta.top()] > p[i]){
				t = sta.top();
				sta.pop();
				ans = max(ans ,(i-t)*p[t] );  
			}
			// 由于p[i]这个值左边可能向左扩展
			// 所以直接将i的位置改到它能扩展的最左位置
			// 这样求面积遍历数组只要从左到右一遍过 
			sta.push(t); 
			p[t] = p[i];
		}
	}
	while(!sta.empty()) sta.pop();
	cout << ans << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	while(cin >> n && n){
		for(int i=1;i<=n;i++){
			cin >> p[i];
		}
		solve();
	}
	

	return 0;
}
Prev
2021-07-21 12:27:00 # ACM
Next