POJ 2559 单调栈 Histogram
这个题目是一个好朋友给我讲的方法，我按照自己的理解，敲出来代码。 所以把算法流程和代码贡献出来，希望和大家共同学习。
题目大意：
给出一个柱形统计图(histogram), 它的每个项目的宽度是1， 高度和具体问题有关。 现在编程求出在这个柱形图中的最大面积的长方形。
例如：
7 2 1 4 5 1 3 3
7表示柱形图有7个数据，分别是 2 1 4 5 1 3 3， 对应的柱形图如下，最后求出来的面积最大的图如右图所示。
分析：
如果采用枚举的方式，如果当前我们枚举项是 i = 0, 即 height = 2,
我们用另外两个变量 j 和k 向左和向右两个方向搜素，找到第一个 小于 height的下标，这样我们就找到了用 i 项作为高度长方形了。
我们假设 -1位置，和最右高度都是无穷小。
例如：
i = 0, j = -1, k = 1, 最后的面积是 (k - j - 1) * height = 2
i = 1, j = -1, k = 7, 最后面积是( k - j - 1) * height = 7;
...
i = 3, j = 2, k = 5 面积是 ( k - j - 1) * height = 8
枚举出所有的长方形的同时，然后得到最后的面积。
不过这样的程序的时间复杂度是 O(n^2)
我们如何能仅仅做一次，就求出这个面积呢？
观察：
当我们扫扫描到第一个高度 H1 = 2的时候，我可以标记它的起始位置1， 因为我们还不知道它将向右扩展到什么地方，所以继续扫面。
当遇到第二项 H2 = 1, 因为这项比之前的小，我们知道，用H1做高度的长方形结束了，算出它的面积。
同时这个时候，我们多了一个高度H2，用它做长方形高度的长方形起始位置应该是在哪里呢？ 因为H1的高度比H2要高，所以这个起始位置自然是H1所在的位置。
为了模拟上面的过程，我们引入单调栈~
我们先定义我们我们要保存的每一项数据
struct Node
{
int height;
int startPosition;
};
用来描述某一个高度，和这个高度的起始位置。
然后我们按照高度来组织成单调栈。我们来看一下它是如何工作的。
为了不用考虑堆栈为空的情况，我们用插入栈底 一个高度（0， 0）的项。
数据：
2 1 4 5 1 3 3
这样初始化
(0 , 0)
I = 1
当扫描到(2， 1）时候，因为高度2 大于栈顶，插入
(0, 0), (2, 1)
I = 2:
当扫描到1的时候，因为1小于栈顶高度2， 我们认为栈顶的那个高度应不能再向右扩展了，所以我们将它弹出
这个时候扫描到 i = 2;
高度是 (i - 1(H1.startIndex)) * H1.height = 2;
我们得到一个面积是2的长方形。
同时我们发现高度是1的当前高度，可以扩展到 H1所在的下标，所以我们插入( 1, 1) 堆栈变成
(0, 0), (1, 1) 因为(2, 1)已经不能向右伸展了，已经被弹出了
i = 3
(0, 0), (1, 1), ( 4 3)
i = 4
(0, 0), (1, 1), (4, 3), (5, 4)
i = 5
这个时候当前高度小于栈顶高度，我们认为栈顶已经不能向右扩展，所以弹出，并且获得面积 ( i - H5.startindex) * H5.height = (5 - 4 ) * 5 = 5
弹出这个元素后，其实(4, 3)的高度也要比 1 大，所以把这个也弹出来，同样方式获得面积 8.
最后我们的堆栈是
(0, 0) , (1, 1)
i = 6
(0, 0), (1, 1), ( 3, 6)
i = 7
(0, 0), (1, 1), (3, 6)
i = 8
最后一步是有点特殊的，因为我们必须要把所有的元素都弹出来，因为栈里面的高度，都坚持到了最后，我们要把这些高度组成的长方形拿出来检测。
我们可以假设扫面到8的时候，高度是0,（最小值）
弹出(3,6)获得面积 (8 - 6 ) * 3 = 6
弹出(1, 1)获得面积(8 - 1) * 1 = 7
最后的面积是8.
代码如下：
[cpp]
Memory: 2116K Time: 454MS
Language: C++ Result: Accepted
Source Code
#include <stdio.h>
#include <stack>
using namespace std;
struct Node
{
long long height;//一个高度值
int startIdx; //这个高度值的起始位置
Node(long long _height, int _idx):height(_height), startIdx(_idx)
{
}
};
long long gHeights[100000];
long long GetMaxArea(int nItem)
{
int i;
stack<Node> s;
long long height;
s.push(Node(-1, 0));//将最小高度加入堆栈，防止堆栈弹空
int currentPosition;
long long maxArea = 0;//记录最大面积
long long curArea;
for( i = 0; i <= nItem ; i++)
{
currentPosition = i + 1;//获得当前 位置
if( i == nItem)//这时候，我们认为到达最后，我们要弹空栈
{
height = 0;
}
else
{
height = gHeights[currentPosition-1];
}
Node t(height, currentPosition);//当前节点
while( s.top().height > height)
{
t = s.top();
s.pop();
curArea = (currentPosition - t.startIdx) * t.height;//按照某个高度的 开始和结束的位置，获得面积
if(curArea > maxArea)
{
maxArea = curArea;
}
}
s.push(Node(height, t.startIdx));
}
return maxArea;
}
int main()
{
int nItem;
while(scanf("%d", &nItem) != EOF && nItem)
{
int i;
for( i = 0; i < nItem; i++)
{
scanf("%lld", gHeights + i);
}
printf("%lld\n", GetMaxArea(nItem));
}
return 0;
}
作者：hopeztm
补充：软件开发 , C++ ,
