首页 > 其他 > 详细

单调栈入门题

时间:2019-09-01 20:31:11      阅读:75      评论:0      收藏:0      [点我收藏+]

单调栈的题, 不知道是不是模板。。。

思想很重要, 保证栈内元素递增, 一旦单调性被破坏, 一直取出栈内元素并进行计算, 直到满足单调性, 成功的将模拟时的复杂计算进行简化与转化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;

const int mx = 1e6 + 50;
const int inf = 1e9;

inline void fre(){ freopen("sign1.in", "r", stdout); freopen("sign1.out", "w", stdout); }

ll st[mx], top, w[mx], a[mx];
int n;

int main(){
    //fre();
    while(scanf("%d", &n) == 1 && n) {
        top = 0;
        ll ans = 0;
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        a[n+1] = 0;
        
        for(int i = 1; i <= n+1; i++) {
            if(a[i] > st[top]) st[++top] = a[i], w[top] = 1;
            else{
                int width = 0;
                while(a[i] <= st[top] && top){
                    width += w[top];
                    ans = max(ans, (ll)width * st[top]);
                    top--;
                }
                st[++top] = a[i]; w[top] = width+1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}




单调栈入门题

原文:https://www.cnblogs.com/Maktub-blog/p/11443326.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!