@TOC

剑指offer 30 包含min函数的栈 LeetCode155

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 $O(1)$。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：

各函数的调用总次数不超过 20000次

注意：本题与主站 155 题相同：https://leetcode-cn.com/problems/min-stack/

[HTML_REMOVED]

解题思路

使用一个额外的 minStack作为辅助栈，栈顶元素为当前栈中最小的值。
在对栈进行 push 入栈和 pop 出栈操作时，同样需要对 minStack 进行入栈出栈操作，从而使 minStack 栈顶元素一直为当前栈中最小的值。在进行 push 操作时，需要比较入栈元素和当前栈中最小值，将值较小的元素 push 到 minStack 中。

Java代码

class MinStack {
    Stack<Integer> stack;//实际数据栈
    Stack<Integer> minStack;//辅助栈，栈顶一直存储当前最小元素，数据个数和实际数据栈中个数一致

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();

    }

    public void push(int x) {
        stack.push(x);
        //辅助栈为空或者当前入栈元素小于之前的最小值，说明当前元素就是最小值
        if(minStack.isEmpty() || x < minStack.peek()){
            minStack.push(x);
        }else{//辅助栈顶元素仍然是最小的，让他再次入栈
            int temp = minStack.peek();
            minStack.push(temp);    
        }
    }

    public void pop() {
        stack.pop();
        //数据栈弹出了一个元素，辅助栈相应弹出一个元素
        minStack.pop();
    }

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

    public int min() {
        return minStack.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.min();
 */