数据结构/算法|连续最大区域面积系列 POJ 2082，2559，2796，3494，1964，3250 数据结构

http://hi.baidu.com/tomspirit/blog/item/22ac940b4b8386c23ac76305.html

http://hplonline20100103.blog.163.com/blog/static/136136434201004004444/

先上函数

void RectangularArea() { int i; high[0 ] = high[n + 1 ] = -1 ; //初始化边界，防止越界判错for (i = 1 ; i <= n; i ++)//把left[], right[]赋值为本身left[i] = right[i] = i; for (i = 1 ; i <= n; i ++) { while (high[left[i] - 1 ] >= high[i])//确定l[i]的最高左位置left[i] = left[left[i] - 1 ]; } for (i = n; i >= 1 ; i --) { while (high[r[i] + 1 ] >= high[i])//确定r[i]的最高右位置right[i] = right[right[i] + 1 ]; } int ans = 0 ; for (i = 1 ; i <= n; i ++) ans = Max(high[i] * (right[i] - left[i] + 1 ), ans); //得到最大的连续矩形面积（单位长度是1）printf("%d/n" , ans); }

函数功能是求连续的最大平面矩形的面积。
函数本质是运用栈的思维。
栈：先进后出，栈在写入的时候只用了个top标记栈顶，每次入栈top ++，但实际stack[]已有数组没有变化，top只是一个指向的作用。
而这个函数的left[], right[]数组就等同于top,具有指向作用。
但是得到的left[i]/right[i]是比本来left[i]/right[i]高的最左和最右位置（满足DP的子问题重叠性质），而这个位置就是具有指向意味。
这是关键代码，下面的练习是以之为基础的。
POJ PKU 2559
直接套用上面函数
POJ PKU 3494
2维的最大矩形覆盖，加个连续行的递推判断，注意数组类型要用__int64
if(str)
a[i][j] = a[i-1][j]+1;
POJ PKU 1964
同 3494
POJ PKU 2796
同 2559 底边是high[left[i]] —— high[right[i]]之和，
读入的时候可以预处理个数组 h1[i] += h1[i - 1] + h[i];
POJ PKU 3250
栈，逆向思维，后面的牛被前面的牛看到。
【数据结构/算法|连续最大区域面积系列 POJ 2082，2559，2796，3494，1964，3250】POJ PKU 2082
同2796，恶心的描述，最后画下图就清晰了。