栈取最小值

• 思路
• 代码
• 图解

思路

如何用O(1)的时间取到栈的当前最小值，默认是不存在的，因为栈就是先进后出这一个特点，如果还能O(1)取值，那这么完美的话，其他的数据结构就没必要存在了。

方法1：用HashMap去记录min，但是取min-1的值依然很麻烦
方法2：借助另一个栈MinStack来操作，元素入栈Stack，同步也入栈MinStack当前最小值，元素出栈，MinStack也同步出栈。

代码

import java.util.Stack;

/**
 * 求栈元素最小值
 * 借助另一个栈MinStack来操作，元素入栈Stack，同步也入栈MinStack当前最小值，元素出栈，MinStack也同步出栈
 */
public class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val < minStack.peek()) {//val和minStack的栈顶元素去比较
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
    }

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

    public int top() {
        return minStack.pop();
    }

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

    public static void main(String[] args) {
        MinStack stack = new MinStack();
        stack.push(7);
        stack.push(6);
        stack.push(8);
        stack.push(4);
        stack.push(9);
        stack.push(3);
        System.out.println(stack.getMin());//3
        stack.pop();
        System.out.println(stack.getMin());//4
    }
}

图解