Simple Java solution using two build-in stacks


  • 15
    Z

    Here is my simple code for minStack, using two build in Java stack to store the stack and min values separately.

    class MinStack {
        // stack: store the stack numbers
        private Stack<Integer> stack = new Stack<Integer>();
        // minStack: store the current min values
        private Stack<Integer> minStack = new Stack<Integer>();
        
        public void push(int x) {
            // store current min value into minStack
            if (minStack.isEmpty() || x <= minStack.peek())
                minStack.push(x);
            stack.push(x);
        }
    
        public void pop() {
            // use equals to compare the value of two object, if equal, pop both of them
            if (stack.peek().equals(minStack.peek()))
                minStack.pop();
            stack.pop();
        }
    
        public int top() {
            return stack.peek();
        }
    
        public int getMin() {
            return minStack.peek();
        }
    }

  • 0
    C

    If I operate as follows: push(5), push(1), push(3), getMin(), getMin().
    I will get 1 and 5, not the right answer: 1 and 3.
    As when I push(3), 3 >1, 3 will not be pushed in minStack.
    How do you think?


  • 0
    Z

    getMin() will not pop the numbers out.


  • -4
    S

    Hi zkfairytale ,

    When you use getMin() method, you only get the returned value on the top of the min stack but without removing it from the stack. So whenever how many times you use getMin(), you always get 1 as 1 is the smallest number among three and it is on the top of the stack.

    If you pop the stack, however, you only pop the value on the stack of the STACK but not the minStack. With the only exception is that the the value on the top of the stack is also the minimum value currently.

    Stack: MinStack

    5 5

    1 -----

    3 1


  • 0
    I

    I like your answer, My solution uses heap and need 2 * n space to save both heap and stack, since yours spend space less than 2 * n and is easier to conduct. Thanks for your share.


  • 0
    U
    This post is deleted!

  • 0
    Z

    the getMin() is not supposed to pop any number out, just like the peek().

    if you read my code carefully, you will find I do pop minStack in the pop() function.
    'if (stack.peek().equals(minStack.peek()))
    minStack.pop();'

    Thanks,


  • 2
    V

    if (stack.peek().equals(minStack.peek()))

    why a "==" wouldn't work here... can someone help me figure it out?


  • 0
    Z

  • 0
    V

    thank you so much!!


  • 0
    M

    @ideno
    I had a similar solution with heap. But remember insertion and deletion into a heap is O(log n), not constant.


  • 0
    J

    @zkfairytale said in Simple Java solution using two build-in stacks:

    hi, I used/walked through your solution. Why am I getting such a high runtime (~110ms). Besides commenting out my code a lot so I could understand what was happening, I did not change anything. Also, I am unfamiliar with Java but does '<=' mean less than, or less than or equal to?


  • 0
    F

    @vickyrabbit I used to have the same problem. The stacks are defined with type Integer, when you peek or pop the stack, you get the (Object) Integer type.
    equals() checks for equality in the value but "==" only checks for reference equality. Obviously, the top of two stacks are stored in different memory locations, so if you only use "==", you will get false.


Log in to reply
 

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