155. Min Stack

Question

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.

Thinking:

• Method

class MinStack {
    private LinkedList<Integer> stack;
    /** initialize your data structure here. */
    public MinStack() {
        this.stack = new LinkedList<Integer>();
    }
    public void push(int x) {
        this.stack.addFirst(x);
    }
    public void pop() {
        this.stack.removeFirst();
    }
    public int top() {
        return this.stack.get(0);
    }
    public int getMin() {
        int min = this.stack.get(0);
        ListIterator<Integer> it = this.stack.listIterator(0);
        while(it.hasNext())
            min = Math.min(min, it.next());
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

• Method 2:使用优先级队列存储数据

class MinStack {
    private Stack<Integer> stack;
    private PriorityQueue<Integer> pq;
    /** initialize your data structure here. */
    public MinStack() {
        this.stack = new Stack<Integer>();
        pq = new PriorityQueue<>();
    }
    public void push(int x) {
        this.stack.push(x);
        this.pq.add(x);
    }
    public void pop() {
        int remove = stack.pop();
        pq.remove(remove);
    }
    public int top() {
        return this.stack.peek();
    }
    public int getMin() {
        return this.pq.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

• Mthod 3: 构造一个新的栈用于存储最小值。

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    public void push(int x) {
        if(!stack.isEmpty())
            minStack.push(Math.min(x, minStack.peek()));
        else
            minStack.push(x);
        stack.push(x);
    }
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

二刷

二刷的时候想到的是通过一个队列来保存对于每一个节点而言当前的最小值。同时对两个数据结构进行操作从而保存出最小值的信息。

class MinStack {
    private Stack<Integer> stack = null;
    private LinkedList<Integer> list = null;
    /** initialize your data structure here. */
    public MinStack() {
        this.stack = new Stack<Integer>();
        this.list = new LinkedList<Integer>();
    }
    public void push(int x) {
        stack.push(x);
        if(list.size() == 0)
            this.list.add(x);
        else
            this.list.add(Math.min(this.list.getLast(), x));
    }
    public void pop() {
        this.stack.pop();
        this.list.pollLast();
    }
    public int top() {
        return this.stack.peek();
    }
    public int getMin() {
        return this.list.getLast();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Amazon session

class MinStack {
    private Stack<Integer> nums;
    private Stack<Integer> min;
    /** initialize your data structure here. */
    public MinStack() {
        this.nums = new Stack<>();
        this.min = new Stack<>();
    }

    public void push(int x) {
        nums.push(x);
        if(this.min.isEmpty()) min.push(x);
        else{
            min.push(Math.min(x, min.peek()));
        }
    }

    public void pop() {
        nums.pop();
        min.pop();
    }

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

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

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */