单调栈

每个$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;
}

利用单调栈算法，找到每一个数左侧和右侧第一个小于自己的数，则两个数间隔的长度乘以当前数的高度即为一个备选答案。从所有答案中选择最大值即可，时间复杂度 $O(n)$。

关于单调栈的内容，可以自行在网上搜索。以下给出一个模板。

#include <stdio.h>
#include <vector>
#include <algorithm>
typedef long long i64;
// 1-indexed
template <typename T, typename F>
struct nearest_bound
{
    int n;
    std::vector<T>& a;
    std::vector<int> pre, suf;
    F f;
    bool op(int x, int y) { return f(a[x], a[y]); }
    // pre[i] = 0 or suf[i] = n + 1 means pre/suf nearest bound do not exist.
    nearest_bound(F _f, std::vector<T>& _a) : f(_f), n(_a.size() - 1), a(_a), pre(_a.size(), 0), suf(_a.size(), _a.size())
    {
        std::vector<int> s;
        for (int i = 1; i <= n; ++i)
        {
            while (s.size() && !op(s.back(), i)) s.pop_back();
            if (s.size()) pre[i] = s.back();
            s.push_back(i);
        }
        s.clear();
        for (int i = n; i; --i)
        {
            while (s.size() && !op(s.back(), i)) s.pop_back();
            if (s.size()) suf[i] = s.back();
            s.push_back(i);            
        }
    }
};
int n;
int main()
{
    auto f = [](int a, int b) { return a < b; };
    scanf("%d", &n);
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    nearest_bound<int, decltype(f)> near_lower_bound(f, a);
    i64 ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        int tmp_l = near_lower_bound.pre[i] + 1, tmp_r = near_lower_bound.suf[i] - 1;
        ans = std::max(ans, 1ll * (tmp_r - (tmp_l - 1)) * a[i]);
    }
    printf("%lld", ans);
}