考点：暴力法及单调栈优化。

暴力法思路：

• 对于每个矩形，求出它左侧能扩展的最大宽度，右侧能扩展的最大宽度

• 由矩形高度以及左右两侧能扩展的宽度，求出每个矩形能得到的面积

• 最大面积为答案

代码：

#include <iostream>

using namespace std;

const int N = 1010;
int h[N];
int n;
int main()
{

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> h[i];
    int res = 0;//最大面积
    for(int i = 1; i <= n; i++)
    {
        int l, r;
        for(int j = i; j >= 1; j--)//左侧边界
        {
            if(h[i] > h[j]) break;
            l = j;
        }

        for(int j = i; j <= n; j++)//右侧边界
        {
            if(h[i] > h[j]) break;
            r = j;
        }
        res = max(res, h[i] * (r - l + 1));
    }
    cout << res;
}

时间复杂度:遍历两遍数组，所以为 O(n^2)。

空间复杂度：没有开辟与输入有关的空间，空间复杂度为 O(1)。

单调栈优化：

在找某个矩形左侧边界的时候，是找到左侧第一个比该矩形低的矩形的位置。

即求出某个数左侧第一个比它小的数字，可以使用单调栈。

右侧同理。

单调栈的相关知识可以看下： https://mp.weixin.qq.com/s/PHv7sr-ZnJ2wGoH9s67elw （文章参考了y总对于单调栈知识的讲解）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int h[N];//h 存储输入的矩形
int l[N];//l 存储每个矩形左侧第一个不能扩展的位置。
int r[N];//r 存储每个矩形右侧第一个不能扩展的位置。
int q[N];//单调栈
int n;//数据个数

void get(int b[])//求解每个矩形第一个不能扩展的位置。
{
    int tt = 0;
    for(int i = 1; i <= n; i++)//遍历矩形，求出每个矩形第一个不能扩展的位置
    {
        while(h[q[tt]] >= h[i]) tt--;//构造单调栈:栈顶对应的矩形高度大于等于当前矩形高度，栈顶出栈，直到栈顶元素对应的矩形高度小于当前矩形高度。
        b[i] = q[tt];//当前矩形第一个不能扩展的位置。
        q[++tt] = i;//当前矩形位置入栈
    }
}

int main()
{

    cin >> n;//输入矩形个数
    for(int i = 1; i <= n; i++)
        cin >> h[i];//输入每个矩形高度

    get(l);//得到每个矩形左侧第一个不能扩展的位置。
    reverse(h + 1, h + 1 + n);//翻转一下矩形的顺序
    get(r);//得到每个矩形右侧第一个不能扩展的位置。
    reverse(h + 1, h + 1 + n);//把矩形位置翻转回原来状态
    long long res = 0;//结果可能超出 int 最大值，用 long long 存储 
    for(int i = 1, j = n; i <= n; i++, j--)//求解每个矩形能获得的最大面积，
    {
        res = max(res, h[i] * (n + 1 - r[j] - l[i] - 1ll));// n + 1 - r[j]：右侧第一个不能扩展的位置，l[i]：左侧第一个不能扩展的位置，n + 1 - r[j] - l[i] - 1ll:矩形的宽度
    }

    cout << res;
}

时间复杂度：求边界 O(n)，求每个矩形能获得面积 O(n)。总时间复杂度 O(n)。

空间复杂度：开辟了栈，存储扩展边界的数组，空间复杂度为 O(n)。

附带解题情况：

21 ms 的为暴力法耗时。

18 ms 的为单调栈优化后耗时。

有问题直接评论即可，求点赞。