难度中等1370
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
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.提示：
-231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
思路：
对于这里的 top() 比较简单，等会直接返回栈顶的元素即可。
而这道题要我们记录最小值，首先我们想到的，就是用一个临时变量 min 进行记录，但是这种方法在一些情况下会出错，比如：
所以这种方法是行不通的！
那该怎么办？
- 解答： 这个时候得用另一个栈来存储每次出现的最小值！
这就是我们的新的方法，很显然是可以的！因为如果 pop 掉了 st 中的元素，那我们就同时把 minst 的元素 pop 掉！
🐛 这种方法还可以优化一下，假设这个 st 中的元素总比 minst 的栈顶元素（即最小值）要大，那我们没必要对这些大的值进行 minst 的入栈，这样子我们就会导致 minst 的过多重复的元素，有点冗余，所以我们考虑一下可以优化一下：
- 对于下一次出现的最小值进行判断，如果比 minst 的栈顶元素要大，那就没必要入 minst ，只有比 minst 中栈顶的值小或者等于才进！
- 当要 pop 的时候，我们只需要判断要删除的元素是否与 minst 栈顶的元素相同，若相同则删掉即可。
class MinStack {
public:
//对于两个stack都无需初始化，因为对于自定义类型编译器会调用其构造函数初始化
MinStack()
{
}
void push(int val)
{
st.push(val);
if(minst.empty() || minst.top() >= val)
{
minst.push(val);
}
}
void pop()
{
if(minst.top() == st.top())
{
minst.pop();
}
st.pop();
}
int top()
{
return st.top();
}
int getMin()
{
return minst.top();
}
private:
stack<int> st;
stack<int> minst;//用于记录最小值
};