设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这里我们的方式是定义一个辅助站，如果新的元素插入的时候比我们原有的辅助栈的栈顶元素小，辅助栈就入栈，如果比辅助栈的栈顶元素更大，就不入栈。
在出栈的时候，如果辅助栈的栈顶元素和原有栈的栈顶元素相等的话，就弹出栈。
class MinStack {
public:
//这个删掉也能过，因为它会默认生成一个minstack()
MinStack() {
}
void push(int val) {
_st.push(val);
if(_minst.empty()|| val <=_minst.top())
{
_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;
};
//如果说我有大量的重复数据应该怎么办
//比方说我们插入了10w个1
//我们这道题有没有优化的空间
//可以加一个计数器
//也就是说这个minst中，新的数据栈顶元素小就更新，比栈顶元素大就不更新，跟栈顶元素相等就让计数器++
一开始我也是认为上面这种算法就可以了，因为可以通过测试用例了，直到一位读者给我指出了优化的方向，再次真的非常感谢这位读者提出的宝贵建议
然后也就是说，如果我们的入栈顺序是3->2->2->1，然后这样的话，我们的最小栈也是要入3->2->2->1这样重复的栈就会导致我们的空间开销非常大。
在此我们采用二元组的形式pair，每一次入栈，就判断一下当前元素是否比最小栈栈顶的元素小，如果比最小栈的栈顶元素小，我们就往最小栈的栈顶push一个二元组，二元组的第一个位置记录当前push进去的元素是什么，第二个位置记录当前push的元素一共有几个
这样的话，我们上面的3->2->2->1中，我们的2就变成用二元组<2,2>来记录了，当pop的时候，也是如果主栈pop了一次2，那么我们的最小栈栈顶的<2,2>变成<2,1>，当主栈再pop一次2，那我们的最小栈就将<2,1>整个弹出。
class MinStack {
public:
//这个删掉也能过，因为它会默认生成一个minstack()
MinStack() {
}
void push(int val) {
_st.push(val);
if(_minst.empty()|| val <_minst.top().first)
{
pair<int, int> tmp = make_pair(val, 1);
_minst.push(tmp);
}
else if(val==_minst.top().first)
{
_minst.top().second++;
}
}
void pop() {
if(_minst.top().first==_st.top())
{
if(_minst.top().second==1)
{
_minst.pop();
}
else{
_minst.top().second--;
}
}
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top().first;
}
private:
stack<int> _st;
stack<pair<int,int>> _minst;
};
//如果说我有大量的重复数据应该怎么办
//比方说我们插入了10w个1
//我们这道题有没有优化的空间
//可以加一个计数器
//也就是说这个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();
*/可以看到现在的代码的效率比之前高了很多。
