LeetCode.155.Min Stack 最小栈

题目描述

155 Min Stack
https://leetcode-cn.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.

---

相似题目

LeetCode.155.Min Stack 最小栈
LeetCode.剑指offer.059.最大队列

---

解题过程

数据栈+最小栈

这道题标准的解法是用两个栈，一个存放数据，一个存放当前最小值，空间换时间。
把两个栈封装在一个栈中，其中的一个栈存放正常的元素，另一个栈 minStack 只存当前最小值。
push：数据栈正常操作。比较当前元素和最小栈minStack的栈顶，比栈顶还小则进栈，否则push原栈顶。
pop：数据栈正常操作。最小栈minStack也pop
getMin：直接返回最小栈栈顶

push，pop，top，getMin 时间复杂度都是 O(1)，空间复杂度 O(n)

这里还可以有个优化，最小栈并不和数据栈同步更新，只是每次push遇到小于等于栈顶的才放入。pop时如果出栈的数据就是最小栈栈顶最小栈，则最小栈也pop。

private static class MinStack {
    private Deque<Integer> minStack;
    private Deque<Integer> dataStack;
    /** initialize your data structure here. */
    public MinStack() {
        minStack = new LinkedList<>();
        dataStack = new LinkedList<>();
    }

    public void push(int x) {
        dataStack.push(x);
        minStack.push(minStack.peek() != null && minStack.peek() < x ? minStack.peek() : x);
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

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

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

栈中存储Pair(value, min)

栈中存储当前值 value，和当前最小值 min

栈+最小堆(优先队列)

没想到很好的思路，用 栈 + 优先队列（最小堆） 实现的。

push 优先队列offer O(logn)
pop 优先队列remove(x) O(n)
top O(1)
getMin O(1)
空间复杂度 O(n)

private static class MinStack {
    private Deque<Integer> stack;
    private PriorityQueue<Integer> priorityQueue;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new LinkedList<>();
        // 优先队列，小顶堆，堆顶永远是最小值
        priorityQueue = new PriorityQueue<>();
    }

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

    public void pop() {
        Integer i = stack.pop();
        // remove(x) 的时间复杂度为O(n)
        priorityQueue.remove(i);
    }

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

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

---

GitHub代码

algorithms/leetcode/leetcode/_155_MinStack.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_155_MinStack.java

---