最小栈 Min Stack

题目

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

题目描述

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.

思路&题解

默认栈的能力是后入先出,没有维护当前最小元素,因此问题的关键是如果保持栈的特性,同时能随时返回最小值。

由于栈可以入栈出栈,因此最小值必定不是一个整形的变量(是多个),我们需要在栈变化后任然能获取到最小值。一个思路是维护一个最小值的栈,每次入栈出栈,我们同步更新这个栈,保持栈大小相同,同时每次插入或者弹出新的最小值。

最小栈-双栈.png

进一步的,我们可以把两个栈合并起来操作

最小栈-双栈-混合.png

class MinStack {

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

    public void push(int x) {
        if(stack.isEmpty()){
            stack.push(x);
            stack.push(x);
        } else {
            int top = stack.peek();
            stack.push(x);
            stack.push(x>top?top:x);
        }
    }

    public void pop() {
        stack.pop();
        stack.pop();
    }

    public int top() {
        int top = stack.pop();
        int value = stack.pop();
        push(value);
        return value;
    }

    public int getMin() {
        return stack.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();
 */

知识点分析

本题重点是记录每次操作过程后的最小元素,由于对取最小元素有时间复杂度的要求:retrieving the minimum element in constant time

取一个数,复杂度是常量级别,说明不能和问题的规模n挂钩,那只能是在栈变化的时候就记录下最小元素,同时需要用数组或者队列来保存每一个状态下的最小元素。 在Java中,栈的实现是Stack接口,可以用两个栈分别保存元素和最小元素。

进一步如果只用一个栈实现,需要对出栈和入栈做一下调整,合并两个栈为一个,本质是一个意思。

  1. 入栈调整:每次入栈,需要同时将新元素和新栈的当前最小元素入栈,栈顶用于放最小元素
  2. 出栈调整:每次出栈,需要连续出两次,将元素和最小元素都弹出
  3. 取栈顶调整:每次取栈顶,需要先把最小元素弹出,然后再取元素,拿到元素后还需要把他再次入栈,这一步可以调用实现的入栈操作(一次入栈两个元素)。
  4. 取最小值:获取栈顶的元素,即为最小值
powered by Gitbook© 小文字 更新: 2019-05-05

results matching ""

    No results matching ""