155. Min Stack (Easy)

https://leetcode.com/problems/min-stack/

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Solutions

1.

class MinStack {

    Stack<Integer> stack;
    Queue<Integer> queue;

    public MinStack() {
        stack = new Stack<>();
        queue = new PriorityQueue<>();
    }

    public void push(int x) {
        stack.push(x);
        queue.offer(x);
    }

    public void pop() {
        int value = stack.pop();
        queue.remove(Integer.valueOf(value));
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return queue.peek();
    }
}

2.

class MinStack {

    Stack<Integer> stack;
    Stack<Integer> min;

    public MinStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (min.isEmpty() || x <= min.peek()) {
            min.push(x);
        }
    }

    public void pop() {
        int value = stack.pop();
        if (min.peek() == value) {
            min.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min.peek();
    }
}

3.

class MinStack {
    class ListNode {
        int value = 0;
        ListNode next = null;

        public ListNode(int v) {
            value = v;
        }
    }

    ListNode stack;
    ListNode queue;

    public MinStack() {
        stack = new ListNode(-1);
        queue = new ListNode(-1);
    }

    public void push(int x) {
        ListNode n1 = new ListNode(x);

        n1.next = stack.next;
        stack.next = n1;

        ListNode n2 = new ListNode(x);
        if (queue.next == null) {
            queue.next = n2;
        } else {
            ListNode ptr = queue;
            while (ptr.next != null) {
                if (ptr.next.value < x) {
                    ptr = ptr.next;
                    continue;
                }

                n2.next = ptr.next;
                ptr.next = n2;
                break;
            }
        }
    }

    public void pop() {
        ListNode val = null;
        if (stack.next != null) {
            val = stack.next;
            stack.next = stack.next.next;
        }

        if (val != null) {
            ListNode ptr = queue;
            while (ptr.next != null) {
                if (ptr.next.value != val.value) {
                    ptr = ptr.next;
                    continue;
                }

                ptr.next = ptr.next.next;
                break;
            }
        }
    }

    public int top() {
        if (stack != null) {
            return stack.next.value;
        }

        return 0;
    }

    public int getMin() {
        if (queue.next != null) {
            return queue.next.value;
        }

        return 0;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""