最小栈＜难度系数＞

题述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类(要求以下接口的时间复杂度都是 O(1))：

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素 val 推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例1：

输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin();   -> 返回 -3.

minStack.pop();

minStack.top();    ->  返回 0.

minStack.getMin();   -> 返回 -2.

提示：

• -2^31^ <= val <= 2^31^ - 1
• pop、top 和 getMin 操作总是在非空栈上调用
• push、pop、top、and getMin 最多被调用 3 * 10^4^ 次

🧷 平台：Visual studio 2017 && windows

核心思想：这里它并没有要求我们使用数组或链表去原生实现，我们这里使用库里的栈，实现接口功能即可。

比如【3, 8, 5, 0 (这里先 push 4 个数据，再 pop 一个数据)】，其次定义 _min 去记录最小值，每次 push 满足条件时就更新 _min，但是当 pop 时就会把 _min 的值删除掉，这时的最小值是 3，但是你怎么写才能知道是 3，你必须得遍历一遍栈里的所有数据，才能知道最小值是 3，而此时的 pop 就不再是 O(1) 了。

所以我们正确的操作应该给两个栈，一个栈存正常值，另一个栈存最小值(注意这里的最小值存多个)，比如【3, 8, 5, 0 (这里先 push 4 个数据，再 pop 一个数据)】，这里在往第一个栈 push 时就记录最小值到第二个栈【3, 0】，如果两个栈里的值 pop 是一样的，那就都 pop，【3】，否则就只 pop 第一个栈。这就是经典的以空间换时间的思想。

边缘问题，比如【3, 8, 5, 0 (这里先 push 4 个数据，再 pop 一个数据，再 push 0，4，0)】，最后一个 0 需要 push 吗 ? 答案是需要的，如果不 push，再 pop 的话就会把最小值给删除(因为这里栈顶的数据是相同的)，此时 getMin 就是 5，但是其实不是。

leetcode原题

class MinStack {public:    //这里其实可以不用写它的构造函数(把它删了也ok),因为_st and _minst都是自定义类型(调用默认构造初始化),同时也不需要实现析构函数(调用默认析构(栈的析构)),同理拷贝构造和赋值也不需要。    MinStack() {    }        void push(int val) {        _st.push(val);        //更新栈        if(_minst.empty() || val <= _minst.top())        {            _minst.push(val);        }    }        void pop() {        //_st必须pop,相同就都pop        if(_st.top() == _minst.top())        {            _minst.pop();        }        _st.pop();    }        int top() {        return _st.top();    }        int getMin() {        //_minist的栈顶就是当前_st的最小值         return _minst.top();    }    stack<int> _st;    stack<int> _minst;};/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */