用单调栈解决最大连续矩形面积问题

单调栈
单调栈是指从栈底到栈顶严格单调的栈，可用于解决最大连续矩形面积问题。
poj2559： http://poj.org/problem?id=2559
给出一个柱形统计图，它的每个项目的宽度是1， 高度给出。 现在编程求出在这个柱形图中的最大连续矩形面积。

设栈内的元素为一个二元组（x, y），x表示矩形的高度，y表示矩形的宽度。
矩形初始高度分别为2,1,4,5,1,3,3
2进栈：(2,1)
1准备进栈，1<2，2要出栈，面积area=2*1=2，1要将宽度累加为2：(1,2)
4进栈：(1.2)(4,1)
5进栈：(1,2)(4,1)(5,1)
1进栈，5出栈area=5*1，4的宽度要加上原来5的宽度4出栈area=4*2，1出栈area不更新，最后1进栈，但宽度要加上出栈的矩形宽度：(1,5)
3进栈：(1,5)(3,1)
3>=3，3出栈，进栈的3宽度累加：(1,5)(3,2)
最后无元素加入，全部出栈每次同上计算面积

源代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
const int N=100005;
struct
{
int x;//高度
int y;//宽度
}stack[N];
/*最大连续矩形面积
单调栈 */
int main()
{
int i,j,n,h;
int sp;
long long maxarea;
stack[0].x=-1,stack[0].y=0;
while(scanf("%d",&n),n)
{
sp=0;
maxarea=0;
for(i=0;i<n;i++)
{
scanf("%d",&h);
if(h>stack[sp].x){//比最大的大，入栈
stack[++sp].x=h;
stack[sp].y=1;
}
else{
long long sum=0;//保存上个栈顶矩形宽度，每次新的栈顶出栈的时候计算面积
while(h<=stack[sp].x)
{
sum+=stack[sp].y;
if(maxarea<sum*stack[sp].x) maxarea=sum*stack[sp].x;
sp--;
}
stack[++sp].x=h;
stack[sp].y=sum+1;//将已经出栈的所有矩形宽度之和sum加到新进栈的
}
/*printf("%dn",i);
for(j=0;j<=sp;j++)
printf("(%d %d) ",stack[j].x,stack[j].y);
printf("n");*/
}
long long sum=0;
while(sp>0)//最后出栈
{
sum+=stack[sp].y;
if(maxarea<sum*stack[sp].x) maxarea=sum*stack[sp].x;
sp--;
}
printf("%lldn",maxarea);
}
return 0;
}

poj3494：http://poj.org/problem?id=3494

需要将题目转化一下，从第2行由左往右开始每次从下到上计算有多少个连续的1，以此为上题的矩形的高度，具体做法是

for(i=1;i<m;i++)
for(j=0;j<n;j++)
if(map[i][j]!=0)
map[i][j]+=map[i-1][j];

#include<iostream>
#include<stdio.h>
#include<string.h>
#define MaxUsr 2010
using namespace std;
struct xxx{
int height;
int width;
}stack[MaxUsr];
int map[MaxUsr][MaxUsr];
int main()
{
int m,n,i,j,h,sp,maxarea;
stack[0].height=-1,stack[0].width=0;
while(~scanf("%d %d",&m,&n))
{
if(m<=0||n<=0) break;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&map[i][j]);
for(i=1;i<m;i++)
for(j=0;j<n;j++)
if(map[i][j]!=0)
map[i][j]+=map[i-1][j];
maxarea=0;
for(i=0;i<m;i++)
{
sp=0;
for(j=0;j<n;j++)
{
h=map[i][j];
if(h>stack[sp].height){
stack[++sp].height=h;
stack[sp].width=1;
}
else{
int sum=0;
while(h<=stack[sp].height)
{
sum+=stack[sp].width;
if(maxarea<sum*stack[sp].height) maxarea=sum*stack[sp].height;
sp--;
}
stack[++sp].height=h;
stack[sp].width=sum+1;
}
}
int sum=0;
while(sp>0)
{
sum+=stack[sp].width;
if(maxarea<sum*stack[sp].height) maxarea=sum*stack[sp].height;
sp--;
}
}
printf("%dn",maxarea);
}
return 0;
}

最后

以上就是繁荣手链为你收集整理的用单调栈解决最大连续矩形面积问题的全部内容，希望文章能够帮你解决用单调栈解决最大连续矩形面积问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。