题目
给一个直方图，求直方图中的最大矩形的面积。例如，下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1，其中最大的矩形是阴影部分。
Input
输入包含多组数据。每组数据用一个整数n来表示直方图中小矩形的个数，你可以假定1 <= n <= 100000. 然后接下来n个整数h1, …, hn, 满足 0 <= hi <= 1000000000. 这些数字表示直方图中从左到右每个小矩形的高度，每个小矩形的宽度为1。 测试数据以0结尾。
Output
对于每组测试数据输出一行一个整数表示答案。
Example
Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Output
8
4000
题目解析
题目要求求出最大矩形的面积，只有求出题目中每个矩形的面积，再进行比较就可以求出最大的矩形面积。
在进一步进行简化，没有必要求出每个矩形的面积，可以在每个位置求出最大矩形的面积，问题就转化到了如何求出每个位置最大的矩形。一种思路是在每个位置都求一遍最大的矩形的面积，在比较即可，但该算法复杂度为O(n2),题目规模为1e5肯定会超时。另一种做法是采用单调栈，求出以当前位置为最小值的区域，即可求出。
代码分析
数据部分const int maxn = 1e6 + 10;long long a[maxn];//放输入的每个矩形的高度long long st[maxn];//单调栈long long r_index[maxn];//放每个矩形最左端的索引long long l_index[maxn];//放最右端对应的索引//选择long long 是因为在最后计算面积时有可能会在int时爆精度
输入数据及初始化
for (int i = 1; i <= n; i++)cin >> a[i];int r = 1;//代表栈的指针int i = 2;//代表要处理的矩形下标st[1] = 1;//第一个矩形入栈l_index[1] = 0;//将第一个矩形左端索引为0
将第i个矩形放入栈中
//这个位置我选的递增栈
若第i个矩形高度大于当前栈顶矩形高度，第i个矩形左边界设置为栈顶元素
st[++r] = i;//矩形入栈l_index[i] = st[r - 1];
若第i个矩形高度小于栈顶矩形高度，就弹出所有高度大于该矩形高度的元素，并将弹出矩阵右边界设置为i,直到栈顶高度小于第i个矩形或者栈为空，然后设置第i个矩阵的左边界为栈顶元素，矩形入栈。
while (r != 0 && a[i] < a[st[r]]){r_index[st[r]] = i;r--;}l_index[i] = st[r];st[++r] = i;
最后，弹出栈中所有剩余元素，并将有边界设置为最大值。
while (r != 0){r_index[st[r]] = n + 1;r--;}
输出答案
for (int i = 1; i <= n; i++){if ((r_index[i] - l_index[i] - 1) * a[i] > Max)Max = (r_index[i] - l_index[i] - 1) * a[i];}cout << Max << endl;
完整代码
#include<cstdio>#include<iostream>using namespace std;const int maxn = 1e6 + 10;long long a[maxn];long long st[maxn];long long r_index[maxn];long long l_index[maxn];//精度要注意一下。int n;int main(){while (true){long long Max = 0;cin >> n;if (n == 0)break;for (int i = 1; i <= n; i++)cin >> a[i];int r = 1;int i = 2;st[1] = 1;l_index[1] = 0;while (i != n + 1){if (a[i] >= a[st[r]]){st[++r] = i;l_index[i] = st[r - 1];}else{while (r != 0 && a[i] < a[st[r]]){r_index[st[r]] = i;r--;}l_index[i] = st[r];st[++r] = i;}i++;}while (r != 0){r_index[st[r]] = n + 1;r--;}for (int i = 1; i <= n; i++){if ((r_index[i] - l_index[i] - 1) * a[i] > Max)Max = (r_index[i] - l_index[i] - 1) * a[i];}cout << Max << endl;}return 0;}
总结
单调栈可以将元素以输入顺序放入栈中，并求出以某个值为最值的区间。
