gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 2559--Largest Rectangle in a Histogram(栈模拟)
 1//栈模拟---157ms
 2//更好的方法，也许是DP吧
 3
 4#include <cstdio>
 5
 6const int SIZE = 100001 ;
 7
 8struct STACK
 9{
10    __int64 ht ;
11    int pos ;
12} ;
13
14STACK stack[SIZE] ;
15int top ;
16
17int N ;
18__int64 height[SIZE] ;
19
20__int64 GetMaxArea()
21{
22    __int64 ans , temp ;
23    int i ;
24    
25    top  = 0 ;
26    
27    stack[top].ht = height[0] ;
28    stack[top].pos = 0 ;
29    ans = height[0] ;
30    height[N] = 0 ;
31
32    for ( i = 1 ; i <= N ; ++i )
33    {
34        if ( height[i] <= stack[top].ht )
35        {
36            while ( top >= 0 && height[i] <= stack[top].ht )
37            {
38                temp = stack[top].ht * (i - stack[top].pos) ;
39
40                if ( temp > ans )
41                    ans = temp ;
42
43                top-- ;
44            }
45            top++ ;
46            stack[top].ht = height[i] ;
47        }
48        else {
49            stack[++top].ht = height[i] ;
50            stack[top].pos = i ;
51        }
52    }
53        
54    return ans ;
55}
56
57int main()
58{
59//    freopen("1.txt", "r", stdin) ;
60
61    int i ;
62
63    while ( scanf("%d", &N) && N != 0 )
64    {
65        for ( i = 0 ; i < N ; ++i )
66        {
67            scanf("%I64d", &height[i]) ;
68        }
69
70        __int64 ans = GetMaxArea() ;
71
72        printf("%I64d\n", ans) ;
73    }
74
75    return 0 ;
76}
posted on 2009-03-05 23:17 巫 阅读(617) 评论(3)  编辑 收藏 引用 所属分类: DP

评论

# re: POJ 2559--Largest Rectangle in a Histogram(栈模拟)[未登录] 2009-07-02 12:26 xc
如果输入的测试数据是 2 1 10
你的代码输出是 1
可正确的输出应该是 10  回复  更多评论
  

# re: POJ 2559--Largest Rectangle in a Histogram(栈模拟)[未登录] 2009-07-02 12:32 xc
48 else {
if (height[i] > ans)
ans = height[i] ;
49 stack[++top].ht = height[i] ;
50 stack[top].pos = i ;
51 }
  回复  更多评论
  

# re: POJ 2559--Largest Rectangle in a Histogram(栈模拟)[未登录] 2009-07-02 12:39 xc
不好意思没看见“ height[N] = 0 ;”这句话  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理