设计一个支持push,pop,top等操作并且可以在O(1)时间内检索出最小元素的堆栈。
push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素
样例
MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin(); --> Returns -4.
minStack.pop();
minStack.top(); --> Returns 3.
minStack.getMin(); --> Returns -1.

解题思路:用一个变量来维护当前栈的最小值,栈中的其他元素与当前栈的最小值有一定的联系。当然,这个最小值随着数据进出栈也是不断更新的。
下面用一组数据来说明:
假设有一个实际栈t1,一个虚拟栈t2,当前栈的最小值value,数据自左向右依次进栈,存放数据如下;
stack_t1: 9 7 5 3 1 10 8 6 4 2
stack_t2: 0 -2 -2 -2 -2 9 7 5 3 1
min_valu: 9 7 5 3 1 1 1 1 1 1

 stack<int>tt;//这里建立虚拟栈,以下函数都是借助虚拟栈对实际栈操作
    int min_v;
    MinStack() {

    }

    void push(int x) {
        if(tt.empty()){
            min_v=x;
            tt.push(x-min_v);
        }else{
            if(x<min_v){
                tt.push(x-min_v);
                min_v=x;
            }else{
                tt.push(x-min_v);
            }
        }
    }

    void pop() {
        if(tt.top()>=0){
            tt.pop();
        }else{
            min_v=min_v-tt.top();
            tt.pop();
        }
    }

    int top() {
        return max(min_v,min_v+tt.top());
    }

    int getMin() {
        return min_v;
    }

根据栈的特点,也可以建另一个栈来维护最小值,无非就是多开点空间。