Simple Java solution 12 line


  • 51
    D

    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() {
        if(stack.peek()==min){ stack.pop(); min=stack.pop(); }
        else stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return min;
    }
    

    }


  • 0

    class MinStack {

    List<Integer> s = new LinkedList();
    List<Integer> q = new LinkedList();
    
    public void push(int x) {
        if(q.isEmpty()) q.add(x);
        else if(x <= q.get(q.size()-1)) q.add(x);
        s.add(x);    
    }
    
    public void pop() {
        if(s.size()<1) return;
        if(top() == q.get(q.size()-1)) q.remove(q.size()-1);
        s.remove(s.size()-1);
    }
    
    public int top() {
        if(s.size()<1) return 0;
        return s.get(s.size()-1);
    }
    
    public int getMin() {
        return q.get(q.size()-1);
    }
    

    }


  • 0
    N

    good idea . push twice if min


  • 0
    N

    good idea . push twice if min


  • 0
    H

    Thanks for sharing such brilliant solution!


  • 1
    C

    Note: This would result in roughly the same memory allocation as two stacks in the worst case (continuously pushing smaller numbers).


  • 0
    J

    very nice sol. Appreciate for sharing!


  • 0
    Z

    what a good idea


  • 0
    Y

    What a good Idea!
    push min and x, if x is min.


  • 0
    T

    Clean solution, thank you!


  • 0
    P

    This is intelligent idea. Idea is to track the minimum value at every element.The same solution in CTCI asks you to maintain an linear memory to track min for each push. Here you are saving space this way.


  • 0
    P

    You can write pop like this to make it shorter.

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

  • 1

    I think there is a problem.
    Example:
    push(2);
    push(0);
    pop();
    pop();
    getMin();

    Last line will return Integer.MAX_VALUE; And in fact it is supposed to be null since the stack is empty now.


  • 1
    S

    @shaoqing The last line won't return Integer MAX_VALUE, because this value is denoted to min in “min=stack.pop();” and correspondingly, the value in stack is deleted by pop()


  • 0

    @SeaLanding yes, it is deleted, but this.min has been set to Integer.MAX_VALUE, and what @shaoqing was saying was that, the getMin() will return Integer.MAX_VALUE, even when stack is empty, and therefore saying the original post is lack of code handling this case!


  • 0

    @SeaLanding Integer.MAX_VALUE is pushed into the stack at the first time push any number in. So even we pop the same amount of time as push, there is extra number in the stack, which is MAX_VALUE. Run the code and you will see.


  • 0

    @xuehaohu You got it.


  • 0

    @shaoqing Guess original code serves a great example to demonstrate the logic to solve the problem, individual submission need more work on handling possible any edge/corner case.


  • 0
    S

    why it won't ac if i change "x<=min" to "x<min" in push function?


  • 0
    S

    @slowdownzhu Oh, i see! Because it will pop() twice when x==min!


Log in to reply
 

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