题解 | #小A的柱状图#

本题是找一个最大面积的矩形，图形是不能变换的，所以我们只需要先确定左右区间，再得到本区间的最小高度便可得到面积。我们可以通过栈的特点，确定第i个位置上的左端点和右端点，高度为$h[i]\mathrm{。}h[i]。$
当我们遍历到第i个位置时，我们以$h[i]h[i]$为矩形高度，对于左右端点而言，增加高度大于等于$h[i]h[i]$的小矩形只会增大面积,而两端小的矩形在之前已经计算完毕，所以不需要更改高度思考要不要加入。记录好左右两端的端点后，计算面积，更新最大值即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<long, long>;
const long long mod = 998244353;
const int N = 1e6 + 250;
//对于第i个位置的左右端点
long long r[N], l[N];
void dilingtian()
{
    int n;
    cin >> n;
    vector<long long> w(n + 1), h(n + 1), sum(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
      //求出宽度前缀和
        sum[i] = sum[i - 1] + w[i];
    }
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    stack<long long> ans;
    for (int i = n; i >= 1; i--)
    {
      //可以扩大面积的小矩形加入
        while (ans.size() && h[i] <= h[ans.top()])
            ans.pop();
      //边界特例
        if (ans.empty())
        {
            ans.push(i);
            r[i] = n + 1;
        }
        else
        {
          //h[ans.top()]<h[i],所以最右端理论上时ans.top()-1
            r[i] = ans.top();
            ans.push(i);
        }
    }
    while (ans.size())
        ans.pop();
    for (int i = 1; i <= n; i++)
    {
      //与右端点同理
        while (ans.size() && h[i] <= h[ans.top()])
            ans.pop();
        if (ans.empty())
        {
            ans.push(i);
            l[i] = 0;
        }
        else
        {
            l[i] = ans.top();
            ans.push(i);
        }
    }
    long long p = 0;
    for (int i = 1; i <= n; i++)
      //更新答案
        p = max(p, (sum[r[i] - 1] - sum[l[i]]) * h[i]);
    cout << p << endl;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while (t--)
        dilingtian();
    return 0;
}