Beats 96.63% C++ Solution using deque


  • 0
    E
    class MinStack {
    public:
        /** initialize your data structure here. */
        MinStack() {}
    
        deque<int> a;
        deque<int> b;
    
        void push(int x) {
            if(a.empty() && b.empty()){
                a.push_back(x);                     // push first number
                b.push_back(x);
            }else{
                a.push_back(x);                   
                if(x<b.back()){             // push the smaller number to the end of b, otherwise to the front of b
                    b.push_back(x);
                }else if(x>b.back()){
                    b.push_front(x);
                }else{
                    b.push_back(x);
                }
            }
        }
        
        void pop() {
            if(a.back()>b.back()){                      // pop the bigger number at the front of b, otherwise pop the last element ( minimum number ) of b
                b.pop_front();
            }else if(a.back()==b.back()){
                b.pop_back();
            }
            a.pop_back();
        }
        
        int top() {
            return a.back();
        }
        
        int getMin() {
            return b.back();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.