Very concise Java solution with Deque interface


  • 12
    B

    The solution is pretty straightforward, keep a minStack besides the underlying stack. During push: push a new item if it's smaller or equals than the current minimum. During pop: if the current item to be popped equals to the top of minStack then pop that one aswell.

    Deque<Integer> stack = new LinkedList<>();
    Deque<Integer> minStack = new LinkedList<>();
    
    public void push(int x) {
        stack.push(x);
        if(minStack.isEmpty() || minStack.peek() >= x) {
            minStack.push(x);
        }
    }
    
    public void pop() {
        int x = stack.pop();
        if(x == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }

  • 0
    P

    Why Deque, you seems to be needing just Queue, am I wrong? I mean the code here is not utilizing the capabilities of Deque and could be done via Queue only?


  • 0
    B

    Actually, you need a LIFO, not a FIFO, and in Java, to use a Stack you should use the Deque interface (the "original" Stack interface is kinda deprecated, see: http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html)


  • 0
    E

    This is my solution using Deque:

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) return Collections.emptyList();
        List<List<Integer>> result = new ArrayList<>();
        Deque<TreeNode> dq = new ArrayDeque<>();
        dq.addFirst(root);
        boolean ltr = true;
        while (!dq.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int i = dq.size(); i > 0; i--) {
                TreeNode node;
                if (ltr) {
                    node = dq.removeFirst();
                    if (node.left != null) dq.addLast(node.left);
                    if (node.right != null) dq.addLast(node.right);
                } else {
                    node = dq.removeLast();
                    if (node.right != null) dq.addFirst(node.right);
                    if (node.left != null) dq.addFirst(node.left);
                }
                level.add(node.val);
            }
            result.add(level);
            ltr = !ltr;
        }
        return result;
    }

Log in to reply
 

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