柱状图求最大矩形面积
题目描述：
给一组非负的整数来表示一个柱状图，设计一个算法获得柱状图中最大矩形的面积。比如，输入如下数据：2,1,4,5,1,3,3 ，其中每个数表示一个柱状条的高度，柱状条的宽度为默认值1，则计算得最大矩形的面积为8，如下图所示。
方法一：思路很简单，以一个柱形为中心往两边扫描，若旁边的柱形高度大于等于该柱形高度，则继续往两边扫。最后记录往旁边扫描了多少距离。
比如图中的系列6，它的高度为3，然后往两边扫描，发现系列7高度大于等于它，而系列5小于它。那么总共扫描距离为2（包括自身），故以系列6为中心的矩形面积为3*2=6。
按上述步骤依次算出每个柱形的矩形面积，取最大值.
等于你在这个高度上画了一条线，只要中间不间断，就算是当前这个矩形面积的大小。
以上思路是之前有听过的。但据说这是单调栈的入门题目，下面是我觉得可能比较复杂的单调栈的一种解法，但很好理解。
方法二：建立一个单调递增栈，所有元素各进栈和出栈一次即可。每个元素出栈的时候更新最大的矩形面积。
设栈内的元素为一个二元组（x, y），x表示矩形的高度，y表示矩形的宽度。
若原始矩形高度分别为2,1,4,5,1,3,3
高度为2的元素进栈，当前栈为（2，1）
高度为1的元素准备进栈，但必须从栈顶开始删除高度大于或等于1的矩形，因为2已经不可能延续到当前矩形。删除（2，1）这个元素之后，更新最大矩形面积为2*1=2，然后把它的宽度1累加到当前高度为1的准备进栈的矩形，然后进栈，当前栈为（1，2）
高度为4的元素进栈，当前栈为（1，2） （4，1）
高度为5的元素进栈，当前栈为（1，2） （4，1） （5，1）
高度为1的元素准备进栈，删除（5，1）这个元素，更新最大矩形面积为5*1=5，把1累加到下一个元素，得到（4，2），删除（4，2），更新最大矩形面积为4*2=8，把2累加到下一个元素，得到（1，4），1*4=4<8，不必更新，删除（1，4），把4累加到当前准备进栈的元素然后进栈，当前栈为（1，5）
高度为3的元素进栈，当前栈为（1，5） （3，1）
高度为3的元素准备进栈，删除（3，1），不必更新，把1累加到当前准备进栈的元素然后进栈，当前栈为（1，5） （3，2）
把余下的元素逐个出栈，（3，2）出栈，不必更新，把2累加到下一个元素，当前栈为（1，7），（1，7）出栈，不必更新。栈空，结束。
最后的答案就是8。
代码如下：
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100005;
struct Elem
{
int height;
int count;
};
Elem stack[N];
int top;
int main()
{
int height, n;
long long ans, tot, tmp;
while (scanf("%d", &n) != EOF && n)
{
top = 0;
ans = 0;
for (int i = 0; i < n; ++i)
{
scanf("%d", &height);
tmp = 0;
while (top > 0 && stack[top - 1].height >= height)
{
tot = stack[top - 1].height * (stack[top - 1].count + tmp);
if (tot > ans) ans = tot;
tmp += stack[top - 1].count;
--top;
}
stack[top].height = height;
stack[top].count = 1 + tmp;
++top;
}
tmp = 0;
while (top > 0)
{
tot = stack[top - 1].height * (stack[top - 1].count + tmp);
if (tot > ans) ans = tot;
tmp += stack[top - 1].count;
--top;
}
printf("%lld\n", ans);
}
return 0;
}
---------------------
方法二转自原文：https://blog.csdn.net/alongela/article/details/8230739
好像还有更好地办法，我之后再学习探究一下
