get MAX() from stack in O(1) using O(1) extra space - cook the code

Sunday 5 November 2017

get MAX() from stack in O(1) using O(1) extra space

#include<bits/stdc++.h>
using namespace std;
class ST{
  int MAX;
  stack<int>s;
    public:
    void push(int data){
        if(s.empty()){
            MAX=data;
            s.push(data);
            return;
        }
        if(MAX>=data){s.push(data); return;}
        s.push(2*data-MAX);
        MAX=data;
    }
    void pop(){
        int t=s.top();
        s.pop();
        if(s.empty()){
            MAX=INT_MIN;
            return;
        }
        if(MAX<t){
            MAX=2*MAX-t;
        }
    }
    int gMAX(){
        return MAX;
    }
};
int main() {
  int n;
    cin>>n;
    ST obj;
    while(n--){
        int c;
        cin>>c;
        if(c==1){
            int data;
            cin>>data;
            obj.push(data);
        }else if(c==2)obj.pop();
        else cout<<obj.gMAX()<<endl;
       
    }
}

No comments:

Post a Comment