单调栈

每个$h_i$是所能构造矩形的高，因此枚举每个$h_i$可以构造的矩形的最大面积，就能得到答案。 问题就转化为以$h_i$为高时，底边最长为多少。 对于每个$h_i$，我们都找到左侧第一个小于它的$h$以及右侧第一个小于它的$h$，中间夹的就是底边长的最大值，也就是熟悉的单调栈问题。

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

typedef long long LL;
const int N = 1e5+5;

int n, h[N];
LL ans;
stack<int> stk_l; //单调栈 1，存下标 
stack<int> stk_r; //单调栈 2，存下标 
int l[N], r[N]; // 分别存储第i个数左侧和右侧第一个小于它的数的下标 

int main() {
	ios::sync_with_stdio(0), 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(!stk_l.empty() && h[stk_l.top()] >= h[i]) stk_l.pop();
		if(!stk_l.empty()) l[i] = stk_l.top();
		stk_l.push(i);
	} 
	//得到右侧第一个小于的数 
	for(int i = n; i >= 1; i --) {
		while(!stk_r.empty() && h[stk_r.top()] >= h[i]) stk_r.pop();
		if(!stk_r.empty()) r[i] = stk_r.top();
		stk_r.push(i);
	} 
	
	int a, b;
	for(int i = 1; i <= n; i ++) {
		a = l[i]; b = r[i];
		if(b == 0) b = n+1;
		ans = max(ans, (LL)h[i]*(b-a-1));
	}
	cout << ans;
	return 0;
}