包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

题解

要求O(1)

利用辅助栈存最小值

入栈时，如果该值 <= 最小值栈中的栈顶的值 ， 就将改值压入最小值栈

出栈，如果出栈元素 == 最小值栈顶元素，则把最小值栈的值一起出栈

private Stack<Integer> stack = new Stack<Integer>();
private Stack<Integer> minStack = new Stack<Integer>();

public void push(int node) {
    stack.push(node);

    if (minStack.empty() || node <= minStack.peek())
        minStack.push(node);
}

public void pop() {
    if (!minStack.empty() && stack.pop() == minStack.peek())
        minStack.pop();
}

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

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