Java accepted solution using one stack


  • 246
    S
    class MinStack {
        int min = Integer.MAX_VALUE;
        Stack<Integer> stack = new Stack<Integer>();
        public void push(int x) {
            // only push the old minimum value when the current 
            // minimum value changes after pushing the new value x
            if(x <= min){          
                stack.push(min);
                min=x;
            }
            stack.push(x);
        }
    
        public void pop() {
            // if pop operation could result in the changing of the current minimum value, 
            // pop twice and change the current minimum value to the last minimum value.
            if(stack.pop() == min) min=stack.pop();
        }
    
        public int top() {
            return stack.peek();
        }
    
        public int getMin() {
            return min;
        }
    }
    

  • 2
    S

    Great solution! Only minor restructure advice for pop() , we can combine the logic to:

     public void pop() {  
         int v = st.pop();  
         if (v == min) {  
           min = st.pop();  
         }  
         if (st.empty()) {  
           min = Integer.MAX_VALUE;  
         }  
       }  
    

    Of course this won't change much, your's already very clean solution


  • 0
    S

    Thank you very much.


  • 5
    C

    Your solution is really cool!!! However, I wonder

        if(stack.empty()){
            min=Integer.MAX_VALUE;
        }
    

    is needed.Becasue at first min=Integer.MAX_VALUE then x <= min so min is pushed into stack. so st.empty() will never be true. Again, thanks for your solution.


  • 0
    S

    Yes, you are right. It is not needed. Thank you very much.


  • 0
    K

    Cool! This looks like VLC version of the most voted "Share my Java solution with ONLY ONE stack"


  • 0
    K

    pop() can be as short as:
    public void pop() {
    if (this.stack.pop() == this.min) {
    this.min = this.stack.pop();
    }
    }


  • 3
    A

    What if the stack is empty and you run getMin(), you'll end up with MAX_VALUE.

    Genious solution though, pop can be simplified as:

        public void pop() {
        int top = stack.pop();
        if (top == min)
            min = stack.pop();
    }

  • 6
    C

    Clever solution. However, beside overhead, this algorithm does not save memory when compare to 2 stacks solution. Basically, the additional push you make when (x <= min) is the same as you push the new min value (i.e., x) to the min stack.

    Also, I implemented this algorithm in C++ and got Output Limit Exceeded error.


  • 20

    For your reference, here is my fast and concise AC Java code.

    I didn't deal with the case when MinStack is empty, because it will raise RuntimeError and should be handled by the Stack class.

    class MinStack {
        Stack<Integer> stack = new Stack<>();
        int min = Integer.MAX_VALUE;
    
        public void push(int x) {
            if (x <= min) {
                stack.push(min);
                min = x;
            }
            stack.push(x);
        }
    
        public void pop() {
            int peek = stack.pop();
            if (peek == min){
                min = stack.pop();
            }
        }
    
        public int top() {
            return stack.peek();
        }
    
        public int getMin() {
            return min;
        }
    }

  • 0

    I think this solution is really cool!


  • 0
    S
    This post is deleted!

  • 0
    S

    for pop()

    public void pop() {
        if (min == stack.pop()) {
            min = stack.pop();
        }
    }

  • 1
    Y

    I like your solution.
    Let me paste the C++ version here.

    class MinStack {
    public:
        MinStack(): m_min(INT_MAX){}
        void push(int x) {
            if(x <= m_min){
                m_stack.push(m_min);
                m_min = x;
            }
            m_stack.push(x);
        }
    
        void pop() {
            if(m_stack.top() == m_min){
                m_stack.pop();
                m_min = m_stack.top();
                m_stack.pop();
            } else {
                m_stack.pop();
            }
            
            if(m_stack.empty()) m_min = INT_MAX;
        }
    
        int top() {
            return m_stack.top();
        }
    
        int getMin() {
            return m_min;
        }
    private:
        stack<int> m_stack;
        int m_min;
    };

  • 5
    G

    I agree. I somehow feel slightly uncomfortable mixing the "minimum values" in addition to the "actual elements" in the stack, and the space complexity is essentially the same as the two-stack approach.


  • 0

    Thanks for sharing your solution.. great work.


  • 0

    cool! easy to understand!


  • 1
    H

    Sorry one question. Why in the push function, we have to push min, and x? Doesn't this cause we push a value twice?


  • 0
    This post is deleted!

  • 0
    B

    @sometimescrazy said in Java accepted solution using one stack:

        public void pop() {
            // if pop operation could result in the changing of the current minimum value, 
            // pop twice and change the current minimum value to the last minimum value.
            if(stack.pop() == min) min=stack.pop();
        }
    

    I am rather confused about this part... I understand the general idea, but how does it work in detail?


Log in to reply
 

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