【广告印刷】

题目描述

最近,afy 决定给 TOJ 印刷广告,广告牌是刷在城市的建筑物上的,城市里有紧靠着的 N 个建筑。afy 决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度,从左到右给出每个建筑物的高度 H1,H2,…,HN,且 0<Hi<=1,000,000,000,并且我们假设每个建筑物的宽度均为 1。要求输出广告牌的最大面积。

输入格式

第一行是一个数 n (n<= 1000,000 )。
第二行是 n 个数,分别表示每个建筑物高度 H1,H2,…,HN,且 0<Hi<=1,000,000,000。

输出格式

输出文件共有一行,表示广告牌的最大面积。

样例数据 1

输入

6
5 8 4 4 8 4

输出

24

先从1~n枚举每个建筑物,维护一个单调队列,其中队尾元素是第i栋建筑最右能延伸到的建筑,然后n~1枚举最左,最后比较一下面积即可。
下面是代码:
stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*