POJ.2559 Largest Rectangle in a Histogram

1.Problem
2559 -- Largest Rectangle in a Histogram (poj.org)

2.Idea
Using stack

3.Source

 int n;  
 int h[N];  
 int L[N], R[N], st[N];  
 void solve()  
 {       
      while (scanf("%d", &n), n) {  
           REP(i, n) scanf("%d", &h[i]);  
           //L  
           int t = 0;  
           for (int i = 0; i < n; i++) {  
                while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
                L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
                st[t++] = i;  
           }  
           //R  
           t = 0;  
           for (int i = n - 1; i >= 0; i--) {  
                while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
                R[i] = (t == 0 ? n : st[t - 1]);  
                st[t++] = i;  
           }  
           long long res = 0;  
           for (int i = 0; i < n; i++) {  
                res = max(res, (long long)h[i] * (R[i] - L[i]));  
           }  
           printf("%lld\n", res);  
      }  
 }