欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最大矩形

程序员文章站 2022-07-07 15:40:22
...

题目:最大矩形
给一个直方图,求直方图中的最大矩形的面积。例如,下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1,其中最大的矩形是阴影部分。
最大矩形

输入:
输入包含多组数据。每组数据用一个整数n来表示直方图中小矩形的个数,你可以假定1 <= n <= 100000. 然后接下来n个整数h1, …, hn, 满足 0 <= hi <= 1000000000. 这些数字表示直方图中从左到右每个小矩形的高度,每个小矩形的宽度为1。 测试数据以0结尾。

输出:
对于每组测试数据输出一行一个整数表示答案。

样例:
输入:
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
输出:
8
4000

解题思路:利用单调栈维护全局每个元素的最小区间(即在这个区间中他最小,这个区间尽可能地大)。然后用区间长度*该元素的值,取最大值即可。这里可以一边输入一边维护;区间的左端点就是弹出栈的元素的左端点中的最小值,右端点是当该元素被弹出时扫到的值。其实可以利用单调栈算两遍的,但是这里优化了一下复杂度,就算了一遍。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[100005];
struct node
{
    long long num;
    int r,l;
}b[100005];
int head=0,tail=-1;//单调栈维护头和尾
int main()
{
    int n;
    while(scanf("%d",&n))
    {
        if(n==0)
        {
            break;
        }
        long long ans=0;
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);//输入
        }
        a[n]=-1;//加个-1,扫到这里的时候全部弹出来
        for(int i=0;i<=n;i++)//-1将所有元素弹出,就扫了一遍
        {
            int l=i;//没有弹出就是i
            while(head<=tail&&b[tail].num>a[i])//判断是否弹出,这里维护的是递减栈,栈顶最大啊
            {
                l=b[tail].l;//左右端点如上述所说
                b[tail].r=i-1;
                ans=max(ans,(b[tail].r-b[tail].l+1)*b[tail].num);
                tail--;
            }
            tail++;
            b[tail].l=l;
            b[tail].num=a[i];
        }
        printf("%lld\n",ans);
    }
}