3210. Maximum Element

帕秋莉_诺蕾姬

用两个栈,其中一个保存最大值

#include<stack>
#include<cstdio>
using namespace std;
int n,q,x,temp;
int main()
{
    scanf("%d",&n);
    stack<int> team,maxu;
    while(n--)
    {
        scanf("%d",&q);
        switch (q)
        {
        case 1:
            scanf("%d",&x);
            team.push(x);
            if(maxu.empty())
                maxu.push(x);
            else if(x>=maxu.top())
                maxu.push(x);
            break;
        case 2:
            temp=team.top();
            team.pop();
            if(temp==maxu.top())//如果pop出的元素等于maxu的栈顶元素则pop maxu
                maxu.pop();
            break;
        case 3:
            printf("%d\n",maxu.top());
        }
    }
}
Andrew-Malcom
#include<bits/stdc++.h>
#define FUCK ios::sync_with_stdio(false);
using namespace std;
int main()
{
    FUCK;cin.tie(0);
    stack<int>S;
    int t;cin>>t;
    int max=0;
    int ssd[100001]={0},index=1;
    while(t--){
        int a;cin>>a;
        if(a==1){
            int b;cin>>b;
            if(b>max){
                max=b;
                ssd[index++]=max;
            }
            else if(b<=max) ssd[index++]=max;
            S.push(b);
        }
        else if(a==2){
            ssd[index-1]=0;
            max=ssd[index-2];
            index--;
            S.pop();
        }
        else if(a==3){
            cout<<ssd[index-1]<<endl;
        }
    }
}
╮ 潜心 ╰

用栈取出栈中的最大值好像挺麻烦的QwQ
我用的是双端队列 队尾操作都是o(1)
优化就是最大值要存下来 每次删除时检查是否删了最大值

test009

hello world!

aiden
#include <iostream>
#include <deque>
using namespace std;

int main()
{
    deque<int> di;
    int n;
    cin >> n;
    while (n--)
    {
        int entry;
        cin >> entry;
        if (entry == 1)
        {
            int element;
            cin >> element;
            di.push_back(element);
        }
        else if (entry == 2)
            di.pop_back();
        else if (entry == 3)
        {
            int max = di.front();
            for (const auto &i : di)
                max = (i > max) ? i : max;
            cout << max << endl;
        }
    }
    return 0;
}
你当前正在回复 博客/题目
存在问题!