初识单调栈

初识单调栈

问题是新的解决之道的催化剂。一个看似简单的题目我写了好几个小时，实在完成不了，查了查，原来需要用到传说中的单调栈。于是，学了一些皮毛。练习了几道。51nod 1437 迈克步​​​≤ x ≤ n）的，最大力量是多少。

分析：

统计所有连续子段中最小值，求最大的一个。

用单纯的两重循环铁定超时，通过观察可以发现，序列和单纯的数值升降有关系。把数字放进一个栈中，升序，遇到小的数字再一个个的弹出来，直到大于等于栈顶元素或者没有元素了。这样不断更新长度是n的连续子段的最小值ans[len]。但是最后得到的数组还不是答案，因为中间过程存在没有涉及到的len。

（开始C++超时了，果断换成纯C，过了）

#include #include #define N 200010int mymax(int a,int b){ return a>b?a:b;}int val[N],dex[N],left_dex[N],top; // 栈val存值，dex存下标，left_dex存第一个小于它的数的下标int ans[N];int main(){ //freopen("cin.txt","r",stdin); int n; while(~scanf("%d",&n)){ memset(ans,0,sizeof(ans)); scanf("%d",&val[1]); dex[1]=1; top=1; int temp=0,len=0; for(int i=2;i<=n;i++){ scanf("%d",&temp); while(temp0;i--){ //处理0 ans[i]=mymax(ans[i],ans[i+1]); } for(int i=1;i

hdu 1506 Largest Rectangle in a Histogram

​​#include using namespace std;typedef long long LL;const int N=1e5+10;LL a[N];int dex[N],top;LL maxm;int main(){ //freopen("cin.txt","r",stdin); int n; LL temp,s; while(cin>>n&&n){ top=0; maxm=0; for(int i=1;i<=n;i++){ scanf("%lld",&temp); while(top>0&&temp=1;i--){ s=a[i]*(n-dex[i-1]); maxm=maxm>s?maxm:s; } printf("%lld\n",maxm); } return 0;}

POJ 2796 Feel Good

​​#include using namespace std;const int N=1e5+10;typedef long long LL;LL a[N],dex[N],top;LL sum[N];LL ans,L,R;int main(){ LL n,temp; while(cin>>n){ top=0; ans=0; for(int i=1;i<=n;i++){ scanf("%lld",&temp); sum[i]=sum[i-1]+temp; while(top>0&&temp<=a[top]){ //wrong -> (sum[i]-sum[dex[top]-1])*a[dex[top]]>ans if((sum[i-1]-sum[dex[top-1]])*a[top]>ans){ ans=(sum[i-1]-sum[dex[top-1]])*a[top]; L=dex[top-1]+1; R=i-1; } top--; } dex[++top]=i; a[top]=temp; } while(top){ if((sum[n]-sum[dex[top-1]])*a[top]>=ans){ ans=(sum[n]-sum[dex[top-1]])*a[top]; L=dex[top-1]+1; R=n; } top--; } printf("%I64d\n%I64d %I64d\n",ans,L,R); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。