在直方图中，一个长方形由其左边界和右边界决定，其最大可能的高度由两者中的最小者决定。记 R(i,j) 为由第 i 个直方柱为左边界，第 j 个直方柱确定的面积最大的长方形。如果 R(i,j) 的面积最大，那么，第 i 个直方柱比它的前一个直方柱（如果存在的话），
即第 i-1 个直方柱要高，而 第 j 个直方柱的高度也比第 j+1 个的要高，否则，由 R(i,j+1) 或 R(i-1,j) 的面积比 R(i,j) 还要大，这违背了 R(i,j) 的最优性。
根据这个观察，我们从第1个直方柱开始，寻找第一个 i, 使得直方柱 i 的高度比 i+1 的大，则 i 是一个可能的右边界，
而 i 之前的每一根直方柱都是可能是左边界（因为 i 是第一个比 i + 1 高的直方柱，所以，在 i 之前的是一个上升的直方柱序列，每一根都比前一根要高）。
这时，我们计算前面所有可能的长方形的面积，并跟当前已知的最大值进行比较，并更新当前已知的最大值（如有必要的话）。然后，我们继续向前搜索第二个这样的 i 。
重复这个过程，直到最后一根直方柱。这样，我们已经遍历了所有可能是最优解的长方形，并取了其中的最大值，因此，该算法是正确的。
至于时间复杂度，似乎还不太明显。对每个直方柱，我们通过跟后一个进行比较就知道其是否为一个可能的右边界。
如果是，则需要对前面的一个上升序列的每个直方住计算其和 i 确定的最大长方形的面积，
这个上升序列最差情况下似乎有 O(n) 长，时间复杂度最差似乎要 O(n2 )。其实不然，只要注意到，每个可能的左边界只会被计算一次，
因此，总的时间复杂度为 O(n)。我们使用一个栈来保存前面的上升直方柱序列，当遇到一个可能的右边界时，
把这些可能的左边界都弹出来，并计算其和右边界确定的长方形面积。显然，每个可能的左边界只会放栈一次。
#include "stdafx.h"
#include <stack>
using namespace std;
typedef stack<int> STACK;
//求出每一个上升长方体的面积最大值
int maxarea(STACK& mystack)
{
int i=0;
int max = 0;
while(!mystack.empty())
{
i++;
int value = mystack.top();
mystack.pop();
int area = value * i;
if (area > max)
{
max = area;
}
printf("value=%d area=%d max=%d\n", value, area, max);
}
printf("----------------------------------------------------\n");
return max;
}
//列出数组中每一个上升的序列
int largestRectangleArea(int arr[], int length)
{
int max= 0;
STACK mystack;
for(int i=0; i<length; i++)
{
mystack.push(arr[i]);
if (arr[i] > arr[i + 1])
{
int area = maxarea(mystack);
if (area > max)
{
max = area;
}
}
}
return max;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[6] = {2, 1, 5, 6, 2, 3};
int length = sizeof(a)/sizeof(int);
int maxarea = largestRectangleArea(a, length);
printf("output the result\n");
printf("maxarea=%d\n", maxarea);
getchar();
return 0;
}