http://poj.org/problem?id=2796
题意：给你一段区间，需要你求出（在这段区间之类的最小值*这段区间所有元素之和）的最大值......
例如：
6
3 1 6 4 5 2
以4为最小值，向左右延伸，6 4 5 值为60.......
思路：解决完为这道题目，我才真正明白了单调栈的原理，它就是以某一个值为最小（最大）值，向这个值的两侧延伸，遇到大于它（小于它）的值，就将它延伸的范围扩大，当然，一般来说，要这样做的算法复杂度为o(n^2)，但是借助栈这个玩意，维护其单调增（减），就可以在o(n)的时间复杂度解决这个问题。将一元素加入栈时，先判断它是否大于(小于)栈顶元素，若是大于（小于）栈顶元素，加入栈。（从这里开始只讲维护单调增栈）否则，将栈顶元素出栈，直到栈顶元素小于要加入栈的元素，在此过程中，需要维护向前延伸和向后延伸的问题，当要加入栈的元素之前有n个栈元素出栈，那么说明这n个出栈的元素都会大于或者等于要入栈的元素，此时，我们需要维护入栈元素可以向前延伸多少个元素（相当于记录它的前面有多少个元素比它大），而每个栈顶元素要向出栈了的元素延伸，因为在出栈了的元素一定是比它的大的元素（根据我维护的是单调增栈）......这样，就在o(n)的时间复杂度内解决了上述问题.........
例如：3 1 6 4 5 2
（3，1，1） （1，2，2） （6，3，3） （4，4，4） （5，5，5） （2，6，6）
首先每个元素自己本身的前后延伸都为1，把3加入栈，1<3，把3出栈，用1的前延伸加上3的前延伸，如此变为（1，1，2），6<1，入栈，变成（1，1，2）（6，3，3），
4<6，将6出栈，4向前延伸，1向后延伸变成（1，1，3） （4，3，4）
5>4，入栈，变成（1，1，3）（4，3，4）（5，5，5）
2<5，5出栈，2向前延伸，4向后延伸，变成（1，1，3）（4，3，5） 2还未入栈（2，5，6）
2<4，4出栈，2向前延伸，1向后延伸，变成（1，1，5） （2，3，6）.....
依次类推，会发现最大的结果在（4，3，5）这里这意味着，以4为最小值的区间范围为3————5，也就是6 4 5
AC代码：
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
int a[];
long long s[];
struct Node
{
int k,l,r;
int num;
};
long long sum,ans;
int main()
{
int n;
while(scanf("%d",&n)==)
{
int x=,y=;
sum=-;
ans=-;
s[]=;
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
if(i==) s[i]=a[i];
else s[i]=s[i-]+a[i];
}
Node t,t1;
stack<Node>q;
t.num=a[];
t.k=t.l=t.r=;
q.push(t);
for(int i=; i<=n; i++)
{
t1.num=a[i];
t1.k=i;
t1.l=t1.r=;
while(!q.empty() && t1.num<=q.top().num)
{
t=q.top();
q.pop();
t1.l+=t.l;
if(!q.empty()) q.top().r+=t.r;
ans=t.num*(s[t.k+t.r-]-s[t.k-t.l]);
if(ans>=sum)
{
sum=ans;
x=t.k-t.l+;
y=t.k+t.r-;
}
}
q.push(t1);
}
while(!q.empty())
{
t=q.top();
q.pop();
if(!q.empty()) q.top().r+=t.r;
ans=t.num*(s[t.k+t.r-]-s[t.k-t.l]);
if(ans>=sum)
{
sum=ans;
x=t.k-t.l+;
y=t.k+t.r-;
}
}
if(n==)x=y=;
printf("%lld\n%d %d\n",sum,x,y);
}
return ;
}
网上写的比较好的代码：
#include<iostream>
#include<stack>
#include<stdio.h>
using namespace std;
#define maxx 110000
__int64 str[maxx],t[maxx];
struct node
{
__int64 num,pre,next; //num记录数值，pre记录向前延伸多少个，next记录向后延伸多少个,k记录本身所处的位置
__int64 k;
};
int main()
{
int n;
while(scanf("%d",&n)==)
{
stack<node>Q;
node tmp;
__int64 ans=-,sum=-,num;
str[]=;
for(__int64 i=; i<=n; i++)
{
scanf("%I64d",&t[i]);
if(i==)
str[i]=t[i];
else
str[i]=str[i-]+t[i];
}
tmp.num=t[];
tmp.pre=;
tmp.next=;
tmp.k=;
Q.push(tmp);
__int64 x=,y=;
for(__int64 i=; i<=n; i++)
{
node tmp1;
tmp1.num=t[i];
tmp1.pre=tmp1.next=;
tmp1.k=i;
while(!Q.empty()&&tmp1.num<=Q.top().num)
{
tmp=Q.top();
Q.pop();
if(!Q.empty())
Q.top().next+=tmp.next;
tmp1.pre+=tmp.pre;
ans=tmp.num*(str[tmp.k+tmp.next-]-str[tmp.k-tmp.pre]);
if(ans>=sum)
{
sum=ans;
x=tmp.k-tmp.pre+;
y=tmp.k+tmp.next-;
}
}
Q.push(tmp1);
}
while(!Q.empty())
{
tmp=Q.top();
Q.pop();
if(!Q.empty())
Q.top().next+=tmp.next;
ans=tmp.num*(str[tmp.k+tmp.next-]-str[tmp.k-tmp.pre]);
if(ans>=sum)
{
sum=ans;
x=tmp.k-tmp.pre+;
y=tmp.k+tmp.next-;
}
} if(n==)x=y=;
printf("%I64d\n%I64d %I64d\n",sum,x,y);
}
return ;
}
不用栈：
//两种不同的代码，这种是不用栈的，代码少，好理解
#include <stdio.h>
#define N 100001
int lef[N],rig[N];
__int64 sum[N],a[N];
int main()
{
int i,j,n;
scanf("%d",&n);
for(i = ; i <= n; ++i)
{
scanf("%I64d",a + i);
sum[i] = sum[i-] + a[i];
lef[i] = rig[i] = i;
}
for(i = ; i <= n; ++i)
while(lef[i] > && a[lef[i]-] >= a[i])
lef[i] = lef[lef[i] - ];
for(i = n-; i; --i)
while(rig[i] < n && a[rig[i]+] >= a[i])
rig[i] = rig[rig[i] + ];
int ll ,rr ; ///答案可以为0，res初始为-1
__int64 res = -,tmp;
for(i = ; i <= n; ++i)
{
tmp = a[i] * (sum[rig[i]] - sum[lef[i]-]);
if(tmp > res)
{
res = tmp;
ll = lef[i];
rr = rig[i];
}
}
printf("%I64d\n%d %d\n",res,ll,rr);
return ;
}