题意：给出一系列的1*h的矩形，求矩形的最大面积。
如图：
可转化为求找一个子序列。 使得这个序列的长度乘以序列最小数最大。
分析：这是一个单调栈的问题，维护栈单调不减。 单调栈 主要是大家要自己枚举，需要找到每个元素 最左能扩展到那 ，最右能扩展到那，当然最小的是你枚举的那个元素。有些细节问题我标有"注意"的地方自己好好想想。和poj 2796有相似的地方。主要是范围不一样，也就是栈的下标有变化了。
Read full article from poj 2559 单调栈 | himdd
如图：
可转化为求找一个子序列。 使得这个序列的长度乘以序列最小数最大。
分析：这是一个单调栈的问题，维护栈单调不减。 单调栈 主要是大家要自己枚举，需要找到每个元素 最左能扩展到那 ，最右能扩展到那，当然最小的是你枚举的那个元素。有些细节问题我标有"注意"的地方自己好好想想。和poj 2796有相似的地方。主要是范围不一样，也就是栈的下标有变化了。
const int A=100005; |
09 | struct{ |
10 | long long h; |
11 | int id; |
12 | }st[A]; |
13 | long long h[A]; |
14 | int main() |
15 | { |
16 | //freopen("1.txt","r",stdin); |
17 | int n; |
18 | while(scanf("%d",&n),n) |
19 | { |
20 | for(int i=1;i<=n;i++) |
21 | { |
22 | scanf("%d",&h[i]); |
23 | } |
24 | h[n+1]=0; |
25 | long long ans=0,tmp; |
26 | int top=1; |
27 | st[top].h=h[1]; |
28 | st[top].id=1; |
29 | for(int i=2;i<=n+1;i++) |
30 | { |
31 | if(st[top].h>h[i]) |
32 | { |
33 | while(top!=0&&st[top].h>h[i]) |
34 | { |
35 | tmp=st[top].h*(i-1-st[top].id+1); |
36 | //st[top].id~i-1的h都是大于等于st[top].h |
37 | //栈顶元素是序列的最小元素 |
38 | if(ans<tmp) |
39 | { |
40 | ans=tmp; |
41 | } |
42 | top--; |
43 | } |
44 | top++; |
45 | st[top].h=h[i]; |
46 | //注意这里st[top].id还是原来的id，因为st[top].id~i-1的h都是>h[i] |
47 | //下一次以h[i]为高计算时，st[top].id~i-1也是要加上的。 |
48 | } |
49 | else//满足栈单调不减入栈 |
50 | { |
51 | top++; |
52 | st[top].h=h[i]; |
53 | st[top].id=i;//注意这里的下标还是本来的i |
54 | } |
55 | } |
56 | printf("%lld\n",ans); |
57 | } |
58 | } |
