全栈开发知识库

54.最小栈

题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

  • 输入: 
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出:
[null,null,null,null,-3,null,0,-2]

解释: 

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

提示:

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次

思路

解题思路:

普通栈的min需要O(n)去遍历。

要做到O(1)，关键问题是: pop之后，如何知道剩余元素的最小值是多少？

单独维护一个minValue变量肯定是不够的，因为pop掉的恰好是当前最小值时，无法知道下一个最小值是什么。

所有解决方案就是: 借用一个辅助栈min_stack，用于存获取stack中每个时刻的最小值。

算法流程:

  • push()方法: 每当push()新值进来时，如果小于等于min_stack栈顶值，则一起push()到min_stack，即更新了栈顶最小值
  • pop()方法: 判断将pop()出去的元素值是否是min_stack栈顶元素值（即最小值），如果是则将min_stack栈顶元素一起pop()，这样可以保证min_stack栈顶元素始终是stack中的最小值
  • getMin()方法: 返回min_stack栈顶即可

min_stack作用分析:

min_stack等价于遍历stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。

相当于给stack中的降序元素做了标记，每当pop()这些降序元素，min_stack会将相应的栈顶元素pop()出去，保证其栈顶元素始终是stack中的最小元素。

复杂度分析:

  • 时间复杂度 O(1) : 压栈，出栈，获取最小值的时间复杂度都为 O(1) 。
  • 空间复杂度 O(N) : 包含 N 个元素辅助栈占用线性大小的额外空间。
class MinStack() {
    val stack = ArrayDeque<Int>()
    val minStack = ArrayDeque<Int>()

    fun push(value: Int) {
        // 没有值就添加，有值就比较添加最小的值
        if (minStack.isEmpty()) {
            minStack.add(value)
        } else {
            minStack.add(minOf(minStack.last(), value))
        }
        stack.add(value)
    }

    fun pop() {
        stack.removeLastOrNull()
        minStack.removeLastOrNull()
    }

    fun top(): Int {
        return stack.last()
    }

    fun getMin(): Int {
        return minStack.last()
    }
}

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> min_stack;
    public MinStack() {
        stack = new Stack<>();
        min_stack = new Stack<>();
    }
    public void push(int x) {
        stack.push(x);
        if(min_stack.isEmpty() || x <= min_stack.peek()) {
            min_stack.push(x);
        }
    }
    public void pop() {
        if(stack.pop().equals(min_stack.peek())) {
            min_stack.pop();
        }
    }

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

    public int getMin() {
        return min_stack.peek();
    }
}
  • 时间：push / pop / top / getMin 全部 O(1)

  • 空间：O(n)，辅助栈与主栈等大

  • 下一题

  • 邮箱 ：charon.chui@gmail.com
  • Good Luck!