单调栈是栈中的元素从栈顶到栈底单调递增或递减。单调栈只能从栈顶部添加或者删除元素，以单调递增栈为例，元素从栈顶到栈底逐渐递增，假设当前元素为e，在入栈时，从栈顶往下找，如果栈顶元素小于当前元素e，则弹出栈顶元素，直到栈顶元素大于等于该元素e，然后将e入栈；出栈时，直接弹出栈顶元素，即可得到栈中当前所有元素的最小值。
由于每个元素都会入栈和出栈一次，因此平摊下来，时间复杂度为O(n).
单调栈示例： poj 2559 Largest Rectangle in a Histogram
题目要求求出由给定的整数数组确定的直方图中，连续的一块最大的矩形面积，其中每个直方列的宽度均为1。
题目解法：
将关注点放在直方图的每个列上，由该列的高度确定的一个矩形（从该点的峰点出发，分别向左和向右延伸，得到最大的宽度，从而得到由该高度确定的矩形的面积）。然后进行一次遍历，得到所有点确定的矩形中最大的一个。
从一点向左（或右）延伸的最大长度（以向左延伸为例），就是从该点出发向左走，如果左边点的高度大于等于该点，则长度加1， 直到遇到的点的高度小于该点的高度则停止，得到最大值。如果使用纯粹的搜索方法，对每个点都做一遍“从该点开始，向左走直到遇到小于它高度的点” 则，复杂度为 O(n^2)，仔细分析可以发现： 如果 进行完 Ai的搜索，得到高度小于Ai的点为P，在进行Ai+1的 搜索的时候，如果 h[i+1] > h[i]， 则直接得到结果i；如果h[i+1] < h[i]，则 从P到i之间的点的高度 肯定大于h[i+1]（因为它们大于h[i])，所以只需要从P开始接着往前找即可。 这样的搜索过程，可以简化为在一个单调递减的栈中进行查找，这个过程可以用单调栈来实现。 在实现的时候，考虑求该点向左延伸时，左边最小的点的索引，并且将索引用栈来存储。
代码实现：注意 long long 的类型，以及 long long result = (right[i] - left[i] + 1)*hist[i]; （在hist 为整数数组时候，需要强制转换为 long long）
不使用单调栈！
#include#include #include #include #include #include #include #include #include #include
#include #include
使用单调栈！
/*除了用数组 left_less_index， right_less_index 记录下来每个位置i处左边/右边第一个高度比height[i]小的位置之外，还可以使用单调栈。栈中存放的是 height数组中的索引【注意，单调栈和单调队列中存放的都是数组元素的索引】。每次计算完位置i，栈顶元素就更新为 i。每次计算的时候，都从栈顶向栈底寻找第一个height[index] 比height[i]小的index, 而将中间过程中的那些不满足条件的index都弹出栈。*///height 数组int height[kMax];//单调栈，栈中存放height数组的索引，从栈顶到栈底 栈中元素（索引）所在位置的height单调递减int mon_stack[kMax];//left_width[i] 表示i处的元素可以向左扩展的最大长度，不包括iint left_width[kMax];//right_width[i] 表示i处的元素可以向右扩展的最大长度，不包括iint right_width[kMax];long long int solve(int n){ int top = -1; for (int i = 0; i < n; i++){ while (top >= 0 && height[mon_stack[top]] >= height[i]){ top--; } left_width[i] = top < 0? i: i - mon_stack[top] - 1; mon_stack[++top] = i; } top = -1; for (int i = n - 1; i >= 0; i--){ while (top >= 0 && height[mon_stack[top]] >= height[i]){ top--; } right_width[i] = top < 0? n - i - 1: mon_stack[top] - i - 1; mon_stack[++top] = i; } long long result = 0; for (int i = 0; i < n; i++){ long long tmp = ((long long)height[i]) * (left_width[i] + right_width[i] + 1); result = max(tmp, result); } return result;}int main(){ int n; while (scanf("%d", &n)){ if (n == 0) break; for (int i = 0; i < n; i++){ scanf("%d", &height[i]); } long long int result = solve(n); printf("%lld\n", result); } return 0;}