https://www.luogu.com.cn/training/596158#information

柱状

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

const int N = 1e5+5;
int n;
int ans;
struct node{
	int id, x;
}a[N];
stack<node> s1, s2;
int f1[N], f2[N];
int main(){
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i].x, a[i].id = i;
	//算出第i个数字右边比它低的第1个位置
	for(int i=n; i>=1; i--){
		while(!s1.empty() && s1.top().x >= a[i].x) s1.pop();
		if(!s1.empty()) f1[i] = s1.top().id;
		else f1[i] = 0;
		s1.push(a[i]);
	}
	///算出第i个数字左边比它低的第1个位置
	for(int i=1; i<=n; i++){
		while(!s2.empty() && s2.top().x >= a[i].x) s2.pop();
		if(!s2.empty()) f2[i] = s2.top().id;
		else f2[i] = 0;
		s2.push(a[i]);
	}
//	for(int i=1; i<=n; i++) cout << f1[i] << ' ';cout << endl;
//	for(int i=1; i<=n; i++) cout << f2[i] << ' ';cout << endl;
	//以第i个为高度 * 左右两边的宽度，求最大值
	int x,ll,rr;
	for(int i=1; i<=n; i++){
		int l, r;  //l表示i左边有几个（包含i）， r表示右边有几个（包含i）
		if(f1[i]==0) r = n-i+1;
		else r = f1[i] - i;
		if(f2[i]==0) l = i;
		else l = i - f2[i];

		ans = max(ans, a[i].x * (l + r - 1));
	}
//	cout << x << " " << ll << ' ' << rr << endl;
	cout << ans;
	return 0;
}