题目

直方图是由一系列在公共基线对齐的矩形组成的多边形。矩形的宽度相等，但高度可能不同。例如，左图显示了由高度为 2、1、4、5、1、3、3 的矩形组成的直方图，单位为 1 是矩形的宽度：

alt

通常，直方图用于表示离散分布，例如文本中字符的频率。请注意，矩形的顺序（即它们的高度）很重要。计算直方图中与公共基线对齐的最大矩形的面积。右图显示了所描绘直方图的最大对齐矩形。

输入包含多个测试用例。每个测试用例都描述一个直方图，并以整数 n 开头，表示它由的矩形数。您可以假设 1 ≤ n ≤ 100000 。然后跟上 n 个整数h1...hn，其中 0 ≤ hi ≤ 1000000000。这些数字按从左到右的顺序表示直方图矩形的高度。每个矩形的宽度为 1。最后一个测试用例的输入后面有一个零。 输出描述: 对于单行上的每个测试用例输出指定直方图中最大矩形的面积。请记住，此矩形必须在公共基线处对齐.

这一篇题解承接了题解46,因为要找一个不超出直方图矩形范围的最大矩形,其实就是在找每一个矩形左右两边最远一个>=他高度的矩形在哪,然后用下标差,乘以那个中心矩形的高度

AC代码

#include<iostream>
#include<stack>
using namespace std;
int a[100010];
int le[100010],ri[100010];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    while(1)//或者把这一堆while(cin>>n && n)
    {
        cin>>n;
        if(n==0) {return 0;}
        else
        {
            for(int i=1;i<=n;++i) {cin>>a[i];}
            stack<int> rig;
          //类比题解46找右边比他高的,这一次找右边最近一个比他矮的,减1就是最后一个 >= 它 的
            for(int i=n;i>=1;--i)
            {
                while(!rig.empty() && a[rig.top()]>=a[i]) {rig.pop();}
                if(!rig.empty()) {ri[i]=rig.top();}
                else {ri[i]=n+1;}//较大的不同就在这里,竟然找不到比他矮的(为空),那么返回右边界+1,再减去一就是最后一个>=他的
                rig.push(i);//存下标,方便计算矩形的底
            }
            stack<int>().swap(rig);//没有rig.clear()//这是与空栈交换,快点清空
          	//这是从左边(与上面反着)开始,找左边最近一个比他矮的,+1就是最后一个>=tade
            for(int i=1;i<=n;++i)
            {
                while(!rig.empty() && a[rig.top()]>=a[i]) {rig.pop();}
                if(!rig.empty()) {le[i]=rig.top();}
                else {le[i]=0;}//同上面那个循环,左边界-1,最后再+1就行
                rig.push(i);
            }
            for(int i=1;i<=n;++i)
            {
              //直接用le是不想再开一个数组了,求矩形的底
                le[i]=ri[i]-le[i]-1;//重点来了 (ri[i]-1)-(le[i]+1)+1,植树原理+类比lower(upper)_bound
            }
            long long res=-1;
            for(int i=1;i<=n;++i)
            {
              //max()比较两个值要同类型
                res=max(res,(long long)a[i]*le[i]);//底乘高
            }
            cout<<res<<'\n';
        }
    }
    return 0;
}