One Stack Java Solution | O(1) time for Push() Pop() Min() | Beats 97 % Java Solution


  • 0
    S

    Simple Idea is to store item and min as we go.

    Ex - When stack is empty and we push -10 , we store the value as -10 and min as -10. Next time when we push -20 , we store the value -20 and with min as -20 (Min of previous min and current value - min of -20 and -10 is -20). and so on.

    public class MinStack {
    
        public Stack<StackNode> ourStack;
        public int min;
    
        /** initialize your data structure here. */
        public MinStack() {
            this.ourStack = new Stack<StackNode>();
            this.min = Integer.MAX_VALUE;
        }
        
        public void push(int x) {
            
             this.min = Math.min(this.min,x);
             StackNode temp = new StackNode(x,this.min);
             ourStack.push(temp);
        }
        
        public void pop() {
            ourStack.pop();
            if(ourStack.isEmpty()){
                this.min = Integer.MAX_VALUE;
            }else{
                this.min = getMin();
            }
        }
        
        public int top() {
            return ourStack.peek().value;
        }
        
        public int getMin() {
            return ourStack.peek().min;
        }
    }
    
     class StackNode {
        public int value;
        public int min;
        
        StackNode(int value, int min ){
            this.value = value;
            this.min = min;
        }
    }

Log in to reply
 

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