Week--5 A - 最大矩形

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


1.png

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

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

Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output
8
4000
实现思路:
依据题意,对于每个小矩形我们需要向前向后分别找到第一个比它低的矩形,此时得到的便为其所能构成的最大矩形,因此我们需要构建单调递增栈来储存当前遍历到的满足条件的最大矩形。最后依次从栈中找出各部分最大值,取最大面积输出。

实现代码如下:

#include<cstdio>
#include<iostream>
#include<stack> 
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;

struct tran{
    long long high;
     int index;
}t[maxn];
int main()
{
    while(true)
    {
        int n;
        cin>>n;
        if(n==0)break;
        stack<tran>s;
        long long ans=0;
        for(int i=1;i<n+1;i++)
        {
            scanf("%lld",&t[i].high);
            t[i].index=i;
            int index;//当前小矩形位置
            int left=i;//最左侧端点
            long long h;//当前小矩形高度

            //查找当前最大矩形
            while(!s.empty()){
                index=s.top().index;
                h=s.top().high;
                if(h>=t[i].high)
                {
                    s.pop();
                    left=index;
                    ans=max(ans,h*(i-left));
                }
                else
                {
                    break;
                }
              }s.push({t[i].high,left});//当前最大矩形入栈
        }
               //找出栈中最大矩形面积
        while(!s.empty()){
            int index;
            int left;
            long long h;
            index=s.top().index;
            h=s.top().high;
                s.pop();
                left=index;
                ans=max(ans,h*(n+1-left));
            }
        printf("%lld\n",ans);
    }
    
  
    return 0;
}

小结:利用单调递增栈(单调递减栈)处理问题可以以O(n)的复杂度处理针对每个数,寻找它和它左 / 右边第一个比它大 / 小的数的值,以及相距多少个数的问题。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 试题编号: 201312-3试题名称: 最大的矩形时间限制: 1.0s内存限制: 256.0MB问...
    YAFree阅读 375评论 0 0
  • 1. file n. 文件;v. 保存文件2. command n. 命令指令3. use v. 使用用途4. p...
    喵呜Yuri阅读 765评论 0 4
  • 题目 给定一个整数map,其中的值只有0和1两种,求其中全是1的所有矩形区域中最大的矩形区域为1的数量。  例如:...
    呤雪情枫阅读 571评论 0 1
  • 就是一些很神奇的数据结构 A:最大矩形 题目: 给一个直方图,求直方图中的最大矩形的面积。例如,下面这个图片中直方...
    大家好我是阿凉阅读 429评论 0 0
  • 计划的几个出行方案都因时间原因放弃了,最终选择了没有太多期待的港澳行,特别是此次无法实现米埔之行,还是很遗憾...
    40b14b8a6983阅读 184评论 0 0