最小栈 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();
 */

知识点分析

powered by Gitbook© 小文字 更新: 2019-04-16

results matching ""

    No results matching ""