C++ using two stacks, quite short and easy to understand


  • 106
    Z
    class MinStack {
    private:
        stack<int> s1;
        stack<int> s2;
    public:
        void push(int x) {
    	    s1.push(x);
    	    if (s2.empty() || x <= getMin())  s2.push(x);	    
        }
        void pop() {
    	    if (s1.top() == getMin())  s2.pop();
    	    s1.pop();
        }
        int top() {
    	    return s1.top();
        }
        int getMin() {
    	    return s2.top();
        }
    };

  • 18
    X

    The question doesn't say if the stack is empty, what should getMin() return. Your code will return INT_MAX.
    I think it's better to change

    if (x <= getMin())  s2.push(x);
    

    to:

     if (s2.empty()||x <= getMin())  s2.push(x);

  • 0
    O

    nice utilizing two stacks!! Luv this thoughts!


  • 2
    H

    it is fine using stacks for implementing stacks? Or should we ask the interviewer before using any data structure.


  • 0
    F

    It is great!!!! When the first min number is deleted ,your program can still provide the second min ! Smart!!!


  • 0
    L

    nice solution, reminds me of another problem using two heaps. Very brilliant!


  • 0
    M

    push(-2);
    push(0);
    push(-3);

    pop();
    pop();

    getMin()// we can't get 0. any problem?


  • 0
    A

    wouldn't s2 grow bigger and bigger in some case?


  • 0
    M

    @mengmee getMin()// we get -2. it's OK.


  • 0
    S

    the solution is smart!!!


  • 0
    M

    very smart!!!!!!


  • 0
    H

    For those who may have been struggling with this approach like me, make sure you include the case where x = getMin() in the push definition:

    void push(int x) {
        s1.push(x);
        if (s2.empty() || x <= getMin())  s2.push(x);	    
    }

  • 2
    Y

    @haditab
    That 's correct! Because x == getMin() is necessary in case of duplicate minimum.
    For example,

    push(0);
    push(1);
    push(0);
    pop();
    getMin();
    

    If x == getMin() is NOT included in push definition

    void push(int x) {
        s1.push(x);
        if (s2.empty() || x <= getMin())  s2.push(x);	    
    }
    

    the s2 would be empty when getMin() is executed.


  • 0
    Y

    @mengmee 0 is the max in your case


  • 1
    M

    @zjchenRice
    Hi, I try to change some lines in push and pop and curiously find something I can't explain...

        void push(int x) {
    	    s1.push(x);
    	    if (s2.empty() || x <= getMin())  s2.push(x);	 
                else(s2.push(getMin()));
        }
        void pop() {
                s2.pop();
    	    s1.pop();
        }
    

    Why this would work but changing s2.empty() to s1.empty() doesn't?


  • 0
    F

    I also noticed that if you change getMin() in pop() to s2.peek(), then you won't pass the tests because for s1.top() == getMin() sometimes we might have null == null, which is also true. LOL


Log in to reply
 

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