算法题：实现最大（小）栈

##题目

实现一个最大（小）栈，即可随时拿出当前栈中最大（小）的元素

##解题思路

这是一道非常经典的面试题，目题目也不难，但还是很能考察开发人员的基本功的，所以面试官很容易脱口就问到这个题

这道题目的要求其实就是实现一个特殊的栈

这个栈能够随时拿到栈中所有元素的最大（小）值

这就是题目所有的要求了

所以在已有栈的基础上稍加改进就能实现

比较简单的办法就是使用两个栈来实现这个特殊的栈

其中一个栈stack正常进出元素

另外一个栈stackMax（stackMin）在进元素的时候，与栈顶的元素做一个比较

如果大于（小于）栈顶元素，则正常入栈

如果小于（大于）栈顶元素，则将当前栈顶的元素再次入栈

注意：当前元素栈顶并不出栈

出栈的时候就跟随stack正常出栈

这样就能保证stackMax（stackMin）跟stack的高度永远一致

并且栈顶的元素永远是最大（小）值

##算法图解

以最大栈为例进行图解演示

定义两个栈，和一堆需要入栈的元素

图片

当栈为空的时候，正常入栈

图片

当栈不为空的时候，stack栈正常入栈

stackMax栈中，则需要将入栈元素“3”与栈顶元素“1”进行比较

“3”>“1”，所以将“3”正常入栈

图片

stack栈仍然正常入栈

stackMax栈中，则需要将入栈元素“1”与栈顶元素“3”进行比较

“3”>“1”，所以将栈顶元素“3”，再次入栈

图片

依次类推，知道所有元素入栈

在这个过程中，stackMax栈的栈顶元素，始终是最大元素

图片 图片 图片 图片

##代码实现

public class MaxHeap {
    private final Stack<Integer> stack;
    private final Stack<Integer> stackMax;

    public MaxHeap() {
        this.stack = new Stack<>();
        this.stackMax = new Stack<>();
    }

    public Integer peekMax() {
        return stackMax.peek();
    }

    public Integer push(Integer item) {
        if (stack.isEmpty()) {
            stackMax.push(item);
        } else {
            if (item > stackMax.peek()) {
                stackMax.push(item);
            } else {
                stackMax.push(stackMax.peek());
            }
        }
        stack.push(item);
        return item;
    }

    public Integer peek() {
        return stack.peek();
    }

    public Integer pop() {
        stackMax.pop();
        return stack.pop();
    }
}

文/戴先生@2021年11月18日

---end---