Simple Java Solution using Two Stacks in O(1)


  • 4
    S

    Feel free to share my solution using an auxiliary stack to store the minimum element(s).

    class MinStack {
            Stack<Integer> mainStack = new Stack<Integer>();
            Stack<Integer> minStack = new Stack<Integer>();
            
            public void push(int x) {
                mainStack.push(x);
                if (minStack.empty()) {
                    minStack.push(x);
                } else if (minStack.peek() >= x) {
                    minStack.push(x);
                }
            }
        
            public void pop() {
                int poppedElement = mainStack.pop();
                if (poppedElement == minStack.peek()) {
                    minStack.pop();
                }
            }
        
            public int top() {
                return mainStack.peek();
            }
        
            public int getMin() {
                return minStack.peek();
            }
        }

  • 0
    L

    The minDeque is the same size as the main deque.

    class MinStack {
        Deque<Integer> deque=new ArrayDeque<Integer>();
        Deque<Integer> minDeque=new ArrayDeque<Integer>();
        
        public void push(int x) {
            deque.push(x);
            
            if(minDeque.isEmpty()){
                minDeque.push(x);
            }else{
                if(x<=minDeque.peek()){
                    minDeque.push(x);
                }else{
                    minDeque.push(minDeque.peek());
                }
            }
        }
    
        public void pop() {
            if(!deque.isEmpty()){
                deque.pop();
                minDeque.pop();
            }
        }
    
        public int top() {
            return deque.peek();
        }
    
        public int getMin() {
            return minDeque.peek();
        }
    }

Log in to reply
 

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