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

100 阅读 0 评论 66 点赞

我是靠谱客的博主繁荣手链，这篇文章主要介绍用单调栈解决最大连续矩形面积问题，现在分享给大家，希望可以做个参考。

单调栈
单调栈是指从栈底到栈顶严格单调的栈，可用于解决最大连续矩形面积问题。
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)
最后无元素加入，全部出栈每次同上计算面积

源代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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，以此为上题的矩形的高度，具体做法是

复制代码

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

然后按照上题的做法，每一行做一次，最后取最大值。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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;
}