hdu1506 Largest Rectangle in a Histogram 单调栈

单调栈的一个简单应用，似乎在艾教那写过……今天又写了一遍，就这样吧……
题意：给你一排不等高矩形，让你从中划出一个面积最大的矩形
思路：用单调栈求出每竖条矩形能到达的最右端点和最左端点，枚举计算即可
链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1506

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
using namespace std;
struct node
{
	long long x;
	int id;
};
int main()
{   long long a[100005];
    int r[100005],l[100005];
    int i,j,k,m,n;
	while(~scanf("%d",&n) && n)
	{   long long ans=-1;
	   	for(int i=1;i<=n;i++)scanf("%I64d",&a[i]);
	   	stack<node>s;
	   	while(!s.empty())s.pop();
	    node temp;
	    temp.id=1;
	    temp.x=a[1];
	    s.push(temp);
	   	for(int i=2;i<=n;i++)
	   	{ node temp;
	   	  if(!s.empty())temp=s.top();
		  if(a[i]>=temp.x || s.empty())
		  { 
		    node tempp;
			tempp.id=i;
			tempp.x=a[i];
			s.push(tempp);	
		   }
		  else
		  if(a[i]<temp.x)
		  {
		   	while(a[i]<temp.x && !s.empty())
		   	{
		  	 r[temp.id]=i-1;
			 s.pop();
			 if(!s.empty())temp=s.top();		
			}
			 node tempp;
			 tempp.id=i;
			 tempp.x=a[i];
			 s.push(tempp);  
		   } 	  	
		 }
		 while(!s.empty())
		 {
		  node temp=s.top();
		  r[temp.id]=n; 
		   s.pop();	
		 }
		 
		 
		 
		 
		 while(!s.empty())s.pop();
		 temp.id=n;
		 temp.x=a[n];
		 s.push(temp);
		 for(int i=n-1;i>=1;i--)
		 {
		  node temp;
	   	  if(!s.empty())temp=s.top();
		  if(a[i]>=temp.x || s.empty())
		  { 
		    node tempp;
			tempp.id=i;
			tempp.x=a[i];
			s.push(tempp);	
		   }
		  else
		  if(a[i]<temp.x)
		  {
		   	while(a[i]<temp.x && !s.empty())
		   	{
		  	 l[temp.id]=i+1;
			 s.pop();
			 if(!s.empty())temp=s.top();		
			}
			 node tempp;
			 tempp.id=i;
			 tempp.x=a[i];
			 s.push(tempp);  
		   } 	  	
		 }
		 while(!s.empty())
		 {
		  node temp=s.top();
		  l[temp.id]=1; 
		   s.pop();	
		 }
		//for(int i=1;i<=n;i++)printf("l %d r %d\n",l[i],r[i]); 
	    for(int i=1;i<=n;i++)
		{
			long long tt=(long long)a[i]*(r[i]-l[i]+1);
			if(tt>ans)ans=tt;
			 }	 
		 printf("%I64d\n",ans);
	}	
	return 0;
}

哎，天天在家看片打游戏，命不久矣