C++ | Single stack O(1) approach


#1
    stack<int> stk;
MinStack::MinStack() {
    while(stk.size()>0){stk.pop();}
    
}

void MinStack::push(int x) {
    if(!stk.empty() && x>stk.top()){
        int minval=stk.top();
        stk.push(x);
        stk.push(minval);    
    }
    else{
        stk.push(x);
        stk.push(x);
    }

}

void MinStack::pop() {
    // cout<<"stk:"<<stk.size()<<" ";
    if(!stk.empty()){
        stk.pop();
        stk.pop();
    }
}

int MinStack::top() {
    if(stk.empty()){
        return -1;
    }
    int val=stk.top();
    stk.pop();
    int ans=stk.top();
    stk.push(val);
    return ans;
}

int MinStack::getMin() {
    if(!stk.empty())
        return stk.top();
    return -1;
}

#2

Well, you’re using 2 push operations so eventually, it will take O(2*n) space which is equivalent to 2 stacks.:upside_down_face: