POJ 2082 Terrible Sets 单调栈，前缀和

题目意思：
有很多个矩形，高矮不一。内部能够得到的最大矩形面积。

本题要点：
1、 Left[i], 表示 i 点能到达的右边的下标值， 显然，Left[1] = 1 (最左边一个矩形)
Right[i], 表示 i 点能到达的左边的下标值, Right[n] = n(最右边的一个矩形)
使用单调栈，初始化 Left[i] 和 Right[i] （详细见代码）
2、 题目要求的面积 = 某个矩形i高度 * (矩形i 能向左右延伸的长度)
长度计算方法如下：
前缀和的使用
s[1] = w[1]
s[2] = w[1] + w[2]
…
s[10] = w[1] + w[2] + … + w[10]
比如，求 3到 7 之间的长度时， len = s[7] - s[3 - 1]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;const int MaxN = 50010;
int n;
int w[MaxN];
int h[MaxN];
int Left[MaxN];		//能到达的右边的下标
int Right[MaxN];	//能到达的左边的下标
int s[MaxN];		//宽度w 的前缀和void sovle()
{
    stack<int> s1, s2;		//栈存放的是下标for(int i = n; i >= 1; --i){
    while(!s1.empty() && h[i] <= h[s1.top()])	{
    											s1.pop();}if(!s1.empty()){
    Right[i] = s1.top() - 1;	//栈顶的矩形高度，比当前的矩形高度要低}else{
    							//当前的矩形只能到达前一个Right[i] = n;	// 第i个矩形能到达 最后一个矩形}s1.push(i);}for(int i = 1; i <= n; ++i){
    while(!s2.empty() && h[i] <= h[s2.top()]){
    s2.pop();}if(!s2.empty()){
    Left[i] = s2.top() + 1;}else{
    Left[i] = 1;}s2.push(i);}memset(s, 0, sizeof(s));	// 前缀和for(int i = 1; i <= n; ++i){
    s[i] = s[i - 1] + w[i];	}int ans = -1;				//最大的可能面积int low, high, area;for(int i = 1; i <= n; ++i){
    low = Left[i], high = Right[i];area = (s[high] - s[low - 1]) * h[i];ans = max(ans, area);}printf("%d\n", ans);
}int main()
{
    while(scanf("%d", &n) && n != -1){
    for(int i = 1; i <= n; ++i){
    scanf("%d%d", &w[i], &h[i]);}sovle();}return 0;
}/* 3 1 2 3 4 1 2 3 3 4 1 2 3 4 -1 *//* 12 14 */