poj 2559 Largest Rectangle in a Histogram (单调栈)
题意：给定从左到右多个矩形，已知这此矩形的宽度都为1，长度不完全相等。这些矩形相连排成一排，求在这些矩形包括的范围内能得到的面积最大的矩形，求该面积。所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。
思路：单调栈。。。好久没写了，感觉之前一直也没有完全掌握单调栈的技巧。这回一定要掌握。
对于这道题，我们对于每个位置i，用两个单调栈维护出最左边和最右边最远能到达的位置。然后扫一遍更新最大值。
单调栈部分我用了stl 的stack
细节见注释
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月03日 星期三 04时27分31秒
4File Name :code/poj/2559.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#include <stack>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35int l[N],r[N];
36stack<int>stk;
37int a[N];
38int n;
39int main()
40{
41 #ifndef ONLINE_JUDGE
42 freopen("code/in.txt","r",stdin);
43 #endif
44 while(scanf("%d",&n)!=EOF)
45 {
46 if (n==0) break;
47 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
48 a[0]=-1;
49 a[n+1]=-1;
50 while (!stk.empty()) stk.pop();
51 stk.push(0);
52 int x;
53 for ( int i = 1 ; i <= n ; i++)
54 {
55 for ( x = stk.top() ; a[x]>=a[i] ; x = stk.top()) stk.pop(); //找到栈中第一个（离a[i]最近的）小于a[i]的位置
56 l[i] = x+1;//第一个小于a[i]的位置的右边就是i位置往左最远能达到的不减的位置。
57 stk.push(i); //栈已经处理成单调了，此时可以入栈。
58 }
59
60 //再反向做一次。
61 while (!stk.empty()) stk.pop();
62
63 stk.push(n+1);
64 for ( int i = n ; i >=1 ; i--)
65 {
66 for ( x= stk.top() ; a[x]>=a[i] ; x = stk.top()) stk.pop();
67 r[i] = x-1;// 第一个小于a[i]的位置的左边就是i位置往右最远能达到的不减的位置。
68 stk.push(i);
69 }
70
71 LL ans = 0LL;
72// for ( int i = 1; i <= n ; i++) printf("i:%d l[i]:%d r[i]:%d\n",i,l[i],r[i]);
73 for ( int i = 1 ; i <= n ; i++)
74 ans = max(ans,1LL*(r[i]-l[i]+1)*a[i]);
75
76 printf("%lld\n",ans);
77
78 }
79
80 #ifndef ONLINE_JUDGE
81 fclose(stdin);
82 #endif
83 return 0;
84}