CCF 最大的矩形
2024-08-28 01:54:40
问题描述
试题编号: | 3 |
试题名称: | 最大的矩形 |
时间限制: | 1.0s |
内存限制: | 256.0MB |
问题描述: |
问题描述
在横轴上放了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(n^2)写的没有得满分,学了下O(n)的做法。
题意找出最大面积的长方形。
之前做过类似的题,有O(n)复杂度的做法,用栈维护一个递增的序列,栈中存对应高度的位置。
每遍历一个元素,判断是否是栈中最大的元素,如果不是,把栈顶的元素弹出,并计算以栈顶元素为最大值高度时的长方形面积。
面积的长度为栈顶元素之前的一个元素到当前遍历的元素的之间的长度,边界情况特殊考虑。
注意弹栈是每一次都要判断,比如34555下标01234,如果有等号的时候到3,2弹栈,但是1,0不弹栈。
#include <cstdio>
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
stack<int> s;
int main()
{
int n,data[];
while(scanf("%d",&n)!=EOF)
{
memset(data,,sizeof(data));
for(int i=;i<n;i++)
scanf("%d",&data[i]);
int mx=;
for(int i=;i<n;i++)
{
if(s.empty()) s.push(i);
else
{
while(!s.empty()&&data[i]<data[s.top()])
//注意弹栈是每一次都要判断,
//比如34555下标01234,如果有等号的时候到3,2弹栈,但是1,0不弹栈。
//有没有等号都对
//序列时刻是递增的
{
int ph=s.top();
s.pop();//必须先弹栈
//i-s.top()-1表示>=ph的元素的个数
if(!s.empty())
mx=max(mx,(i-s.top()-)*data[ph]);
else
mx=max(mx,i*data[ph]);
}
s.push(i);
}
}
while(!s.empty())
{
int ph=s.top();
s.pop();
if(!s.empty())
mx=max(mx,(n-s.top()-)*data[ph]);
else
mx=max(mx,n*data[ph]);
}
printf("%d\n",mx);
}
return ;
}
拓展问题是求01矩阵的最大子矩阵。
附上链接:传送门。
最新文章
- jdbc java数据库连接 6)类路径读取——JdbcUtil的配置文件
- iOS中关于NavigationController中preferredStatusBarStyle一直不执行的问题
- Java-坦克大战
- go语言条件语句 if else
- Jquery:ajax跨域请求处理
- C# chart绑定数据的方式整理
- HDU4003 Find Metal Mineral
- SQL SERVER存储过程生成字母+数字的编码
- AMD与commonJS
- C++对C语言register的增强
- C#流程控制语句--分支语句(if,switch,三位运算符)
- Html table、thead、tr、th、td 标签
- 史上最全 40 道 Dubbo 面试题及答案,看完碾压面试官
- 17秋 软件工程 团队第五次作业 Alpha Scrum2
- sqlzoo需要知道的那些事
- 启用了不安全的HTTP方法【转】
- python-数据分析与展示(Numpy、matplotlib、pandas)---1
- mapgis IGServer账号
- Charles proxy tools 移动开发调试
- Bomb HDU 3555 dp状态转移