题目详情
给定直方图,每一小块的height由N个非负整数所确定,每一小块的width都为1,请找出直方图中面积最大的矩形。
如下图所示,直方图中每一块的宽度都是1,每一块给定的高度分别是[2,1,5,6,2,3]:
那么上述直方图中,面积最大的矩形便是下图所示的阴影部分的面积,面积= 10单位。
请完成函数largestRectangleArea,实现寻找直方图中面积最大的矩形的功能,如当给定直方图各小块的高度= [2,1,5,6,2,3] ,返回10。
【解析】
使用一个栈来保存输入柱状条,每个柱状条包含两个信息:(1)柱状条的高度(height);(2)柱状条的宽度(width) 。初始宽度均为单位宽度1。
在随后的入栈和出栈中随时更改柱状条的宽度。
(1)当入栈柱状条的高度大于栈顶柱状条的高度或者栈为空时,柱状条入栈;如图1
(2)当入栈柱状条的高度小于栈顶柱状条的高度时,柱状条出栈,同时计算出栈的柱状条的面积,更新最大矩形面积。同时更新当前柱状条的宽度。如图2
(3)当入栈柱状条的高度等于栈顶柱状条的高度时,柱状条出栈,更新当前柱状条宽度。如图3
(4)如果最后栈不空,只剩高度递增的柱状条。一个一个出栈,更新最大矩形面积。每一个柱状条出栈都要更新前一个柱状条的宽度。如图4
写的不好,勿喷。
【代码】
/*********************************
* 日期:2013-11-24
* 作者:SJF0115
* 题号: 寻找直方图中面积最大的矩形
* 来源:http://hero.pongo.cn/Question/Details?ID=58&ExamID=56
* 结果:AC
* 来源:庞果网
* 总结:
**********************************/
#include<iostream>
#include<stack>
#include<vector>
#include<stdio.h>
#include<malloc.h>
using namespace std;
typedef struct Rec{
int height;
int width;
}Rec;
int LargestRectangleArea(vector<int> &height){
int Max = 0,i;
int n = height.size();
//容错处理
if(n <= 0){
return 0;
}
Rec *rec = (Rec*)malloc(sizeof(Rec)*n);
stack<Rec> stack;
//初始化
for(i = 0;i < n;i++){
rec[i].height = height[i];
rec[i].width = 1;
}
for(i = 0;i < n;i++){
int h = rec[i].height;
//如果栈空或者当前高度大于栈顶的矩形高度的时候就压入栈
if(stack.empty() || h > stack.top().height){
stack.push(rec[i]);
}
else{
int preWidth = 0;
//小于栈顶的矩形高度就弹出栈,更新最大的矩形面积
while(!stack.empty() && h < stack.top().height){
rec[i].width += stack.top().width;
//当前面积
int currentMax = stack.top().height * (stack.top().width + preWidth);
//更新最大值
if(Max < currentMax){
Max = currentMax;
}
preWidth += stack.top().width;
//出栈
stack.pop();
}
//等于栈顶的矩形高度
while(!stack.empty() && h == stack.top().height){
rec[i].width += stack.top().width;
stack.pop();
}
//栈空
if(stack.empty() || h > stack.top().height){
stack.push(rec[i]);
}
}
}
//最后栈中只剩递增的序列
int width = 0;
while(!stack.empty()){
int currentMax = stack.top().height * (stack.top().width + width);
if(currentMax > Max){
Max = currentMax;
}
width += stack.top().width;
stack.pop();
}
return Max;
}
int main(){
int i,n,Max,num;
while(scanf("%d",&n) != EOF){
vector<int> height;
for(i = 0;i < n;i++){
scanf("%d",&num);
height.push_back(num);
}
Max = LargestRectangleArea(height);
printf("%d\n",Max);
}
return 0;
}
【方法二】
【解析】
设柱状图为非负整数数组A, 则最大矩形的高度必定是数组的某一项height[i]。
设f(i) 为以数组第i项的高度为矩形高度时矩形的最大宽度,则最大矩形为max{f(i)*height[i]} (0 <= i < n)
f(i)本身无法动态规划,但若将f(i)拆成左右两部分,则很容易动态规划求解
令left(i)为以数组第i项为矩形高度时矩形左侧最大宽度,
right(i)为以数组第i项为矩形高度时矩形右侧最大宽度,
则f(i) = left(i) + right(i) - 1
【代码】
/*********************************
* 日期:2013-11-25
* 作者:SJF0115
* 题号: 寻找直方图中面积最大的矩形
* 来源:http://hero.pongo.cn/Question/Details?ID=58&ExamID=56
* 结果:AC
* 来源:庞果网
* 总结:
**********************************/
#include <stdio.h>
int left[100001],right[100001];
int largestRectangleArea(const int *height,int n) {
int Max = 0,i,j;
//容错处理
if(height == NULL || n <= 0){
return 0;
}
left[0] = 1;
right[n-1] = 1;
//以数组第i项为矩形高度时矩形左侧最大宽度
for(i = 1;i < n;i++){
//初始为单位宽度1
left[i] = 1;
for(j = i-1;j >= 0;){
if(height[i] <= height[j]){
left[i] += left[j];
//跳到下一个比较对象
j -= left[j];
}
else{
break;
}
}
//printf("第%d项左最大宽度:%d\n",i+1,left[i]);
}
//以数组第i项为矩形高度时矩形右侧最大宽度
for(i = n-2;i >= 0;i--){
//初始为单位宽度1
right[i] = 1;
for(j = i+1;j < n;){
if(height[i] <= height[j]){
right[i] += right[j];
//跳到下一个比较对象
j += right[j];
}
else{
break;
}
}
//printf("第%d项右最大宽度:%d\n",i+1,right[i]);
}
for(i = 0;i < n;i++){
int currentMax = (left[i] + right[i] - 1) * height[i];
if(Max < currentMax){
Max = currentMax;
}
}
return Max;
}
//start 提示:自动阅卷起始唯一标识,请勿删除或增加。
int main()
{
int height[] = {1,2,3,4,3,4,3,2,1};
int max = largestRectangleArea(height,9);
printf("%d\n",max);
return 0;
}
//end //提示:自动阅卷结束唯一标识,请勿删除或增加。
【测试数据】
{1,2,3,4,3,4,3,2,1} 结果: 15
{3,4,5,6} 结果:12
{2,1,2,1,2,1} 结果:6
{2,1,5,6,2,3}结果:10
{2, 1, 4, 5, 1, 3, 3, 1, 2} 结果:9
分享到:
相关推荐
给定直方图,每一小块的height由N个非负整数所确定,每一小块的width都为1,请找出... 请完成函数largestRectangleArea,实现寻找直方图中面积最大的矩形的功能,如当给定直方图各小块的高度= [2,1,5,6,2,3] ,返回10。
CSDN 编程大赛寻找直方图中面积最大的矩形的个人解答,已编译执行通过。
由于个人原因,上次上传的是练习的,有写问题,这是自己修改后的... 直方图中每一块的宽度都是1,每一块给定的高度分别是[2,1,5,6,2,3]; 那么上述直方图中,面积最大的矩形面积 = 10单位
直方图中最大的矩形.md
灰度直方图寻找波峰,vs2010实验,采用了opencv
直方图匹配或叫做直方图规定化都可以,是把原图像的直方图按照给定的直方图加以映射,使新图像的直方图的分布类似于给定的函数。 总共有以下几步: 1.求给定的函数的累积直方图s。 2.求原图像的累积直方图G。 3....
等面积二元子图像直方图均衡 英文文章,名称为image enhancement based on equal area dualistic sub-image
直方图的优势在于它是一种很直观的图表类型,用于在有序的列中显示连续数据。直方图非常适用于较大的数据点集。直方图实质上是一个频率分布图,它会将源数据值归到各个条柱或组距中。列高度表示落在每个条柱中的项目...
对两张彩色图进行直方图匹配并显示匹配前、后的图像和它们的直方图
利用matlab编写的直方图均衡化和直方图匹配的函数
内含两个程序,一个是将函数cvvHist1D改写成用直方块方式绘制直方图,一个是用折线方式绘制直方图。
直方图均衡化、直方图变换、对比度自适应直方图均衡化
灰度直方图,利用matlab实现图像的直方图均衡化
求图像的灰度直方图
2:以一个给定的高斯分布的直方图为参考,对一幅图像进行点运算,使其直方图与参考直方图分布尽量一致,显示处理后图像的累计直方图与参考的累计直方图。使用MFC完成界面编程,程序中包括:打开图像,显示图像,保存...
Qt实现一个图像的灰度直方图。使用QImage读取图像,QCustomPlot实现直方图。Qt实现一个图像的灰度直方图。使用QImage读取图像,QCustomPlot实现直方图。
绘制误差分布直方图,并在每个直方图上面标注该范围对应的数字,且返回一个table统计结果。
本资源不含OpenCV,OpenCV只用来转灰度图(可以删掉相关代码)其余画直方图是自己写的函数。 实验任务 统计灰度图像的直方图 (1)以二进制方式读取一幅 bmp、jpeg 或 png 格式图像的数据,并判断其是否为灰度图像...
直方图均衡化是增强图像对比度的一种方法。当一幅图像灰度级分布不均的时候,可以通过直方图均衡化来重新分布灰度。本文提供了直方图均衡化的C代码。