leetcode: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.

    原问题链接：https://oj.leetcode.com/problems/min-stack/

 

问题分析

    如果之前看过一些关于算法方面的教材的话，会发现这个问题其实并不复杂。我们想想，因为需要获取当前元素的最小值。在每次对栈进行操作的时候，这个最小值可能在栈中间的任何一个地方。要想保留这个最小值，必然需要一个可以记录在某个范围内最小值为多少的结构。

    在加入一个新的元素进来时，我们还需要将新加入的元素和当前最小值做比较，如果新加入的值比当前最小值还要小，则最小值就需要进行修改。同样，当取出一个元素的时候，如果当前值是最小的元素，我们也需要做相应的调整。一种比较简单的保存最小值的结构就是再使用一个栈，这个最小值栈保存着到对应栈顶元素最小值。按照这些讨论，我们可以得到如下的代码：

 

class MinStack {
    private Stack<Integer> itemStack = new Stack<Integer>();
    private Stack<Integer> minStack = new Stack<Integer>();
    
    public void push(int x) {
        if(itemStack.isEmpty() || x < minStack.peek()) {
            itemStack.push(x);
            minStack.push(x);
        } else {
            itemStack.push(x);
            minStack.push(minStack.peek());
        }
    }

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

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

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

     这个实现属于比较懒的办法。就是用一个最小值栈，每个元素都和原来的栈一一对应起来，如果原来的栈要加入的元素是当前最小的，则在两个栈中加入这个元素，否则在原来栈中加入这个元素而在最小值栈中加入它自己栈顶的那个。这种做法稍微有点浪费空间了。不过整体的空间复杂度还是在O(N).

    除了前面这个思路以外，还有一种思路，就是不再和原来栈里的元素一一对应的去存，就只是在最小值栈里保存最小的那个。它的实现和原来的差不多，只有两个方法的差别，push, pop方法的实现如下：

public void push(int x) {
        stack.push(x);
        if(minStack.isEmpty() || x <= minStack.peek()){
            minStack.push(x);
            }
    }

    public void pop() {
        if(stack.peek().equals(minStack.peek())){ 
            minStack.pop();
        }
        stack.pop();
    }

     因为这个问题比较简单，就不再赘述了。