poj_2559 单调栈

题目大意

    给出一个柱形图中柱子的高度，每个柱子的宽度为1，柱子相邻。求出柱形图中可能形成的矩形的最大面积。

题目分析

    以每个柱子（高度为h[i]）为中心，向两边延展求出以该h[i]为高度的矩形的最大宽度w[i]。h[i]*w[i]得到以该柱子为中心的最大矩形面积，遍历一遍之后取最大值即可。 
    关键在于求出以柱子i为中心的两边延展的矩形最大宽度。先考虑柱子i延伸到左边的最大距离：坐标p不断左移，直到h[p] < h[i]，然后i - p即为柱子向左延伸的最大长度。如果直接这么做，复杂度为O(n^2)。显然，如果h[i] > h[i-1]，则left_width[i] 必定为 left_width[i-1] +1， 若查找完left_width[i-1]，则可以通过这个性质直接知道left_width[i]。显然，直接查找存在重复。 
    观察发现，对于当前点i和它之前的距离它最近的满足h[k] < h[i]的点k，若要获得i向左延伸的最大距离，只需要知道k，而k和i中间的那些点j不需要被查询（是否满足h[i] >= h[j])。于是，我们只保存k和i这样的点，以便在查找的时候跳过k和i中间的那些点，于是可以使用单调栈来实现。 
    单调栈中存放元素（点的索引，点的高度），若当前点的高度大于栈顶元素点的高度，则入栈；否则，弹栈，直到当前点的高度大于栈顶元素的高度，然后入栈。此时，当前点i的left_width[i] = i - 入栈之前的栈顶元素的索引。 
    同理，利用单调栈查找向右延伸的最大长度。

    感觉：单调栈/单调队列经常用在需要从某个点i向回查找，且直接查找会出现冗余访问导致复杂度为O(n^2)的问题上。在查找的时候考虑不进行往回找，而是利用数据的单调性质一遍查找，则可将复杂度降为O(n)

实现(c++)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#define MAX_NUM 100005
int gStack[MAX_NUM][2];
int gHeight[MAX_NUM];
int gWidth[MAX_NUM][2];
long long int GetMax(int n){
	memset(gWidth, 0, sizeof(gWidth));
	int top = -1;
	int i = 0;
	while (i < n){
		while (top >= 0 && gStack[top][1] >= gHeight[i]){
			top--;
		}
		if (top >= 0)
			gWidth[i][0] = i - gStack[top][0];
		else{
			gWidth[i][0] = i + 1;
		}
		top++;
		gStack[top][0] = i;
		gStack[top][1] = gHeight[i];
		i++;
	}
	i = n - 1;
	top = -1;
	while(i >= 0){
		while (top >= 0 && gStack[top][1] >= gHeight[i]){
			top--;
		}
		if (top >= 0){
			gWidth[i][1] = gStack[top][0] - i;
		}
		else{
			gWidth[i][1] = n - i;
		}
		top++;
		gStack[top][0] = i;
		gStack[top][1] = gHeight[i];
		i--;
	}
	long long int max = 0;
	for (int i = 0; i < n; i++){
		long long int tmp = (long long int) (gWidth[i][0] + gWidth[i][1] - 1)*gHeight[i];
		max = max > tmp ? max : tmp;
	}
	return max;
}
int main(){
	int n;
	while(scanf("%d", &n)){
		if (n == 0){
			break;
		}
		for (int i = 0; i < n; i++){
			scanf("%d", gHeight + i);
		}
		long long int max = GetMax(n);
		printf("%lld
", max);
	}
	return 0;
}