专栏首页AI那点小事CCF考试——201312-3 最大的矩形

CCF考试——201312-3 最大的矩形

概要

问题描述

  在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是hi。这n个矩形构成了一个直方图。例如,下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

  请找出能放在给定直方图里面积最大的矩形,它的边要与坐标轴平行。对于上面给出的例子,最大矩形如下图所示的阴影部分,面积是10。

输入格式

  第一行包含一个整数n,即矩形的数量(1 ≤ n ≤ 1000)。   第二行包含n 个整数h1, h2, … , hn,相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。

输出格式

  输出一行,包含一个整数,即给定直方图内的最大矩形的面积。

样例输入

6 3 1 6 5 2 3

样例输出

10


思路

分别利用vector和set存储据矩形高度,set的目的是防止重复数据的出现。利用迭代器it对set进行遍历,设置cnt为0,开始统计vector中高度大于it指向的高度的个数存储在cnt当中。若不连续则对阴影面积进行更新,cnt重新置0。


AC代码

#include <iostream>
#include <vector>
#include <set> 
using namespace std;

vector<int> data;
set<int> s;
set<int>::iterator it;
int n,num;
long long ans;

int main()
{
    while(cin>>n){
        for(int i = 0 ; i < n ; i++){
            cin>>num;
            data.push_back(num);
            s.insert(num);          //避免重复元素遍历 
        }
        ans = 0;
        for(it = s.begin() ; it != s.end() ; it++){
            int cnt = 0;
            num = *it;
            for(int i  = 0 ; i < n ; i++){
                if(data[i] >= num){         //连续大于data[i]的矩形个数 
                    cnt++;
                }else{
                    if(ans < num*cnt){      //对最大面积进行更新 
                        ans = num*cnt;
                    }
                    cnt = 0;                //重新统计个数 
                }
            }
            if(ans < num*cnt){
                ans = num*cnt;
            }
        }
        cout<<ans<<endl;
    } 

    return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法训练 删除数组零元素

    从键盘读入n个整数放入数组中,编写函数CompactIntegers,删除数组中所有值为0的元素,其后元素向数组首端移动。注意,CompactIntegers函...

    AI那点小事
  • 黑白卡片

    牛牛有n张卡片排成一个序列.每张卡片一面是黑色的,另一面是白色的。初始状态的时候有些卡片是黑色朝上,有些卡片是白色朝上。牛牛现在想要把一些卡片翻过来,得到一种交...

    AI那点小事
  • 寻找Coder

    请设计一个高效算法,再给定的字符串数组中,找到包含”Coder”的字符串(不区分大小写),并将其作为一个新的数组返回。结果字符串的顺序按照”Coder”出现的次...

    AI那点小事
  • 关关的刷题日记81 – Leetcode 258. Add Digits

    关关的刷题日记81 – Leetcode 258. Add Digits 题目 Given a non-negative integer num, repeat...

    WZEARW
  • HotSpot垃圾回收细节

    ​ 对于存活对象的判断可达性分析过程中,首先需要得到一系列的GCRoots,GCRoots一般选择的是一定存活的对象,例如虚拟机栈中引用的对象 (...

    你的益达
  • 1019. 数字黑洞 (20)

    给定任一个各位数字不完全相同的4位正整数,如果我们先把4个数字按非递增排序,再按非递减排序,然后用第1个数字减第2个数字,将得到一个新的数字。一直重复这样做,我...

    AI那点小事
  • 马蜂窝支付中心架构演进

    为了更好地支持交易业务的快速发展,马蜂窝支付中心从最初只支持基础支付和退款的「刀耕火种」阶段,经历了架构调整的「刮骨疗伤」阶段,完成了到实现综合产品平台形态的「...

    马蜂窝技术
  • 理解Java中锁的状态与优化

    关于锁的知识,按大类来说,通常我们只分乐观锁和悲观锁。但在Java语言里对同步锁的状态又进行了细化通常有无锁状态,偏向锁,自旋锁,轻量级锁,重量级锁,这么做的目...

    我是攻城师
  • 通过支持向量回归和LSTM进行股票价格预测

    人工智能(AI)无处不在。机器学习和人工智能正在彻底改变现代问题的解决方式。应用机器学习的一种很酷的方法是使用财务数据。财务数据是机器学习的一个游乐场。

    代码医生工作室
  • 1064 朋友数 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051

扫码关注云+社区

领取腾讯云代金券