C++ O(1) solution


  • 24
    G
    class MinStack {
    public:
        vector<int> a;
        vector<int> min;
        MinStack() {
            min.push_back(2147483647);
        }
        void push(int x) {
            a.push_back(x);
            if (x < min.back()) {
                min.push_back(x);
            } else {
                min.push_back(min.back());
            }
        }
    
        void pop() {
            a.pop_back();
            min.pop_back();
        }
    
        int top() {
            return a.back();
        }
    
        int getMin() {
            return min.back();
        }
    };

  • 0
    I

    This seems more intuitive than the double stack method.


  • 0
    J

    i wonder there is some defects about your problem about your pop function.if the stack is empty,there must be some wrong with this operation about a.pop_back();Am i wrong?


  • 0
    G

    So the client who calls this method should never do that.


  • 1
    G

    I believe this:

        if (x < min.back()) {
            min.push_back(x);
        } else {
            min.push_back(min.back());
        }
    

    Can be written as:

    min.push_back(min(x, min.back());
    

    Anyway, you are using more space than necessary...


  • 1
    S

    said in C++ O(1) solution:

    2147483647
    I think you could use INT_MAX instead of 2147483647。


  • 2
    F

    In fact you could use only one vector

    
    class MinStack {
        vector<int> a;
        int min;
    public:
        /** initialize your data structure here. */
        MinStack() {
            min = INT_MAX;
        }
        
        void push(int x) {
            if(x <= min) {
                a.push_back(min);
                min = x;
            }
            a.push_back(x);
        }
        
        void pop() {
            int t = a.back(); a.pop_back();
            if (t == min) {
                min = a.back();
                a.pop_back();
            }
        }
        
        int top() {
            return a.back();
        }
        
        int getMin() {
            return min;
        }
    };

Log in to reply
 

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