题目

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

示例

• 示例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.

代码

解法：

class MinStack {

    Stack<Integer> stack;
    Stack<Integer> min; //辅助栈

    /**
        * initialize your data structure here.
        */
    public MinStack() {
        stack = new Stack();
        min = new Stack();
    }

    public void push(int x) {
        stack.push(x);
        if (min.isEmpty()) {
            min.push(x);
        } else {    // 确保弹栈之后，此时辅栈中栈顶仍是最小元素
            Integer pop = min.pop();
            if (x > pop) {
                min.push(pop);
                min.push(pop);
            } else {
                min.push(pop);
                min.push(x);
            }
        }
    }

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

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

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

    }
}

代码分析：1、根据示例，测试的时候首先会传一个对象，所以需要提供构造方法。

2、这道题的重点是要求调用 min、push 及 pop 的时间复杂度都是 O(1)。而且是要求能动态的获取到该栈中最小的值：就是说不管是添加了 m 次也好，删除了 n 次也罢，只要一调用 min() 就能获取到当前最小值。所以，单单用一个变量来记录最小值行不通了。

3、此方法中采用一个栈 min 来记录最小值（不一定要用栈，其他的也能实现）。关键代码:

Integer pop = min.pop();
if (x > pop) {
   min.push(pop);
   min.push(pop);
} else {
   min.push(pop);
   min.push(x);
}

先把栈 min 中栈顶元素弹出 与 新添加进来的元素 x 比较。如果 pop 更小，说明从一开始到现在栈 min 中的最小元素就是 pop，需要把 pop 添加到栈 min 中两次，一次是刚刚被弹出来的现在要添加回去，另一次是作为对应 x 的最小值来添加的。
那如果 x 更小，情况就不同了，需要先添加 pop ，再添加 x : 保证最小的元素一直处于栈 min 的栈顶位置，并且能确保在 x 被删除之后，最小值依然是 pop。

• y总代码

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stackValue;
    stack<int> stackMin;
    MinStack() {

    }

    void push(int x) {
        stackValue.push(x);
        if (stackMin.empty() || stackMin.top() >= x)
            stackMin.push(x);
    }

    void pop() {
        if (stackMin.top() == stackValue.top()) stackMin.pop();
        stackValue.pop();
    }

    int top() {
        return stackValue.top();
    }

    int getMin() {
        return stackMin.top();
    }
};

题目：bao-han-minhan-shu-de-zhan-lcof