题目给出N个数，找出一段区间使得区间最小值乘区间和的值最大 其中N<=100000
分析： 单调队列（单调栈） 求出每个值作为最小值时最长的影响区间，然后枚举判断
这找出最长影响区间应该算是单调队列的最典型的用法了~
具体来说就是入队的时候可以得到影响区间的最左边，出队列的时候可以得到影响区间最右边的值
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 #include <queue> 6 using namespace std; 7 const int maxn=100000+10; 8 const int INF=2147400000; 9 int a[maxn]; 10 long long sum[maxn]; 11 int n; 12 deque<int>q; 13 int L[maxn],R[maxn]; 14 int flag=0; 15 int main(){ 16 while(~scanf("%d",&n)){ 17 memset(L,0,sizeof(L)); 18 memset(R,0,sizeof(R)); 19 sum[0]=0; 20 for(int i=1;i<=n;i++){ 21 scanf("%d",&a[i]); 22 sum[i]=sum[i-1]+a[i]; 23 } 24 for(int i=1;i<=n;i++){ 25 if(!q.empty()&&a[i]<a[q.back()]){ 26 while(!q.empty()&&a[i]<a[q.back()]){ 27 int u=q.back(); 28 R[u]=i-1; 29 L[i]=L[u]; 30 q.pop_back(); 31 } 32 }else{ 33 L[i]=i; 34 } 35 q.push_back(i); 36 } 37 while(!q.empty()){ 38 int u=q.front(); 39 q.pop_front(); 40 R[u]=n; 41 } 42 long long ans=-1; 43 int ansl,ansr,len; 44 for(int i=1;i<=n;i++){ 45 long long u=sum[R[i]]-sum[L[i]-1]; 46 if(ans<u*a[i]||ans==u*a[i]&&len>R-L){ 47 len=R-L; 48 ans=u*a[i]; 49 ansl=L[i]; 50 ansr=R[i]; 51 } 52 } 53 if(flag)cout<<""<<endl; 54 else 55 flag=1; 56 cout<<ans<<endl; 57 cout<<ansl<<" "<<ansr; 58 } 59 return 0; 60 }