hdu1506(Largest Rectangle in a Histogram)单调队列实现 （广告印刷变形）_�少_新浪博客

首先考虑问题需要的时间复杂度如果是o（n）的算法，单调队列是首选。

最终的广告牌一定等于某个建筑物的高度×其能达到的最大长度

现在，建筑物的高度已知，现在只需要知道每个高度能达到的最大长度是多少。由于n是100000，我们只能用O（n）或O（nlogn）的算法。当让完全可以使用rmq（本人太弱还没研究ST算法所以木用 ， 稍后一定补上为大家奉上），在后边的论文中会讲到。

现在讲时间复杂度为o（n）的单调队列的方法。

继续上边的思路，对于每个建筑物，只需要找到其能够扩展到的最大宽度即可。也就是这个建筑物的左右两边的比它低或等于它的建筑物个数。

如何用单调队列呢？

从1~n依次进队，维护一个单调递增的序列（最小队列） （注意que要存 高度方便比较 和 方块的起始位置 ， 方便更新 r ）。

每次加入元素后按照单调队列的入队性质维护其单调性，当然这样做必然会使一些元素出队，出队的元素一定要比当前加入的元素大，也就是说当前元素就是出队的元素能在右侧达到的最远的建筑物！ 然后记录当前元素i-1的位置（距离） 。 

注意，要让

l[1~n]一开始要初始化为n r[1~n]初始化为1 处理极限（就是如果没出过队就是覆盖所有长度） 并且让该元素入队一次（会使当前队列中的所有元素出队），保证每个元素都有其“右极限”的值.

要求“左极限”同理，只需从n~1循环即可

这道题是对单调队列的变形使用。由于问题的结果具有单调性，很好的利用出队元素的特性。

long long n, h[100001], r[100001], l[100001], pos[100001], val[100001];
 7 int main()
 8 {
 9     int head, tail;
10     while(scanf("%ld", &n), n)
11     {
12         head = 0, tail = -1;
13         for(int i=1 ; i<=n ; i++)
14         {
15             scanf("%ld", &h[i]);
16             l[i] = 1;
17             r[i] = n;
18             while(head <= tail && h[i] < val[tail])
19             {
20                 r[pos[tail]] = i-1;
21                 --tail;
22             }
23             pos[++tail] = i;
24             val[tail] = h[i];
25         }
26         head = 0, tail = -1;
27         long long int res = 0;
28         for(int i=n ; i>=1 ; i--)
29         {
30             while(head <= tail && h[i] < val[tail])
31             {
32                 l[pos[tail]] = i+1;
33                 --tail;
34             }
35             pos[++tail] = i;
36             val[tail] = h[i];
37         }
38         for(int i=1 ; i<=n ; i++)
39             res = max(res, (r[i] - l[i] + 1)*h[i]);
40         cout << res << endl;
41     }
42 }

Also check http://www.cnblogs.com/baijin/archive/2013/06/16/3116138.html
Read full article from hdu1506(Largest Rectangle in a Histogram)单调队列实现 （广告印刷变形）_�少_新浪博客