CCF CSP 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
解析
这里一道很经典的题目，许多网站上都有这道题目。题目很容易找到一个O(N2)的解，但是还存在一个更优的O(N)的解。
首先明确几个事实：最大矩形一定以N个矩阵之中的一个为高度。
因此问题可转换成以第i个矩阵为高度的最大面积。
代码
C++
#include "iostream"
#include "stack"
#include "vector"
#include "algorithm"
using namespace std;
int getMaxArea(vector &hist)
{
stack s;
int max_area = ;
int i = ;
int tp, area_with_top;
while(i < hist.size())
{
if(s.empty() || hist[s.top()] <= hist[i])
s.push(i++);
else
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i-s.top()-);
max_area = max(max_area, area_with_top);
}
}
while(!s.empty())
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i-s.top()-);
max_area = max(max_area, area_with_top);
}
return max_area;
}
int main()
{
int N;
vector vec;
cin >> N;
for(int i=; i
{
int val;
cin >> val;
vec.push_back(val);
}
cout << getMaxArea(vec);
}
CCF CSP 201409-2 画图
CCF计算机职业资格认证考试题解系列文章为meelo原创,请务必以链接形式注明本文地址 CCF CSP 201409-2 画图 问题描述 在一个定义了直角坐标系的纸上,画一个(x1,y1)到(x2,y ...
CCF CSP 201403-2 窗口
CCF计算机职业资格认证考试题解系列文章为meelo原创,请务必以链接形式注明本文地址 CCF CSP 201403-2 窗口 问题描述 在某图形操作系统中,有 N 个窗口,每个窗口都是一个两边与坐标 ...
CCF CSP 认证
参加第八次CCF CSP认证记录 代码还不知道对不对,过两天出成绩. 成绩出来了,310分. 100+100+100+10+0: 考试13:27开始,17:30结束,提交第4题后不再答题,只是检查前四 ...
CCF CSP 201609-2 火车购票
题目链接:http://118.190.20.162/view.page?gpid=T46 问题描述 请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配. 假设一节车厢有20排.每一排 ...
CCF CSP 201703-3 Markdown
CCF计算机职业资格认证考试题解系列文章为meelo原创,请务必以链接形式注明本文地址 CCF CSP 201703-3 Markdown 问题描述 Markdown 是一种很流行的轻量级标记语言(l ...
CCF CSP 201703
CCF CSP 2017·03 做了一段时间的CCF CSP试题,个人感觉是这样分布的 A.B题基本纯暴力可满分 B题留心数据范围 C题是个大模拟,留心即可 D题更倾向于图论?(个人做到的D题基本都是 ...
CCF CSP 201609-3 炉石传说
CCF计算机职业资格认证考试题解系列文章为meelo原创,请务必以链接形式注明本文地址 CCF CSP 201609-3 炉石传说 问题描述 (Hearthston ...
CCF CSP 201403-3 命令行选项
CCF计算机职业资格认证考试题解系列文章为meelo原创,请务必以链接形式注明本文地址 CCF CSP 201403-3 命令行选项 问题描述 请你写一个命令行分析程序,用以分析给定的命令行里包含哪些 ...
CCF CSP 201709-4 通信网络
CCF计算机职业资格认证考试题解系列文章为meelo原创,请务必以链接形式注明本文地址 CCF CSP 201709-4 通信网络 问题描述 某国的军队由N个部门组成,为了提高安全性,部门之间建立了M ...
随机推荐
ArcGIS Engine中加载数据
ArcGIS Engine中加载数据 http://blog.csdn.net/gisstar/article/details/4206822 分类: AE开发积累2009-05-21 16:49 ...
ord函数-php
摘录自http://php.net/manual/zh/function.ord.php (PHP 4, PHP 5, PHP 7) ord — 返回字符的 ASCII 码值 说明 int ord ( ...
UDP通讯协议
常见的通讯协议有udp和tcp. 先来简单了解一下这两个协议各自的特点: UDP: --将数据及源.目的封装在数据包中,不需要建立连接: --每个数据包的大小限制在64k以内: --因无连接,是不可靠 ...
使用Visual Studio创建映像向导(Image Sprite)——Web Essential
原版的:Creating Image Sprite in Visual Studio - Web Essential 译者注:有关图片精灵的信息请參阅http://baike.baidu.com/vi ...
Unity Shader入门教程(一)
参考文献:http://www.360doc.com/content/13/0923/15/12282510_316492286.shtml Unity Shader是着色器,将纹理.网格信息输入,得 ...
AngularJS进阶(一)深入理解ANGULARUI路由_UI-ROUTER
深入理解ANGULARUI路由_UI-ROUTER 最近在用 ionic写个webapp 看到几个demo中路由有好几种,搞的有点晕,查下资料研究下,做个笔记,其中大部分为摘抄别人的,做个说明免得被人 ...
SQL Server CTE 递归查询全解(转载)
在TSQL脚本中,也能实现递归查询,SQL Server提供CTE(Common Table Expression),只需要编写少量的代码,就能实现递归查询,本文详细介绍CTE递归调用的特性和使用示例 ...
刚开始学java和刚去工作的时候，1.path路径 2.classpath路径 还有JAVA_HOME相当于/dgs这个路径
把里面bin文件夹下面的可执行文件都配置到path路径下了,以后只要在Dos窗口输入命令就可以运行 无论是在dos窗口下还是在eclispe中只需要配置这个path变量,不需要配置classpath ...
汇编 fsub ,fmul,fdiv,fild,CVTTPS2PI 指令
知识点: 浮点指令 fsub 一.浮点指令fsub 格式 fsub memvar // st0=st0-memvar 知识点: 浮点指令 fmul 一.浮点指令fmul 格式 fmul mem ...
STM32之HAL库、标准外设库、LL库
标准外设库(Standard Peripherals Library),应该是最早推出的版本,以前用STM32F103的时候,用的多 HAL(Hardware Abstraction Layer),硬 ...
