Min Stack

1package pkg5leetcode.interview150;2 3/*4 * Min Stack | LC 1555 * APPROACH: Two stacks track current min alongside values.6 * COMPLEXITY: Time O(1) per op, Space O(n)7 */8import java.util.*;9 10public class interview150_LC155MinStack {11    static class MinStack {12        Deque<Integer> stack = new ArrayDeque<>();13        Deque<Integer> mins = new ArrayDeque<>();14 15        void push(int val) {16            stack.push(val);17            if (mins.isEmpty() || val <= mins.peek()) mins.push(val);18        }19 20        void pop() {21            if (stack.pop().equals(mins.peek())) mins.pop();22        }23 24        int top() { return stack.peek(); }25 26        int getMin() { return mins.peek(); }27    }28 29    public static void main(String[] args) {30        MinStack ms = new MinStack();31        ms.push(-2);32        ms.push(0);33        ms.push(-3);34        check(ms.getMin() == -3, "case1");35        ms.pop();36        check(ms.top() == 0, "case2");37        check(ms.getMin() == -2, "case3");38        System.out.println("all tests passed");39    }40 41    static void check(boolean cond, String name) {42        if (!cond) throw new AssertionError("FAILED: " + name);43        System.out.println("  PASS " + name);44    }45}