手把手带你弄懂最小栈

C++的原生栈，可以实现 push、pop、top，但是要获取最小元素
一种方法是通过暴力搜索，从头到尾遍历整个，那么时间复杂度是 O(n)，不是在常数级获取最小值， 不符合题目的要求。
所以我们可以设置两个栈，一个数据栈 st，用于存放需要存放的数据，一个记录最小值的栈 minst。

会影响当前最小值的操作只有两种一个是 push 一个是 pop

每次 push 时需要改变最小值的情况也有两种 ：
①：当前栈为空，那push的元素一定是最小值
②：当前push的元素 ≤ minst的栈顶元素

每次pop时会改变最小值的情况只有一种
被删掉的正好是最小值：也就是st的栈顶元素 == minst的栈顶元素

#include <bits/stdc++.h>
using namespace std;
stack<int> st;		//正常存数据的栈 
stack<int> minst;	//专门处理最小值的栈 
int main(){
    int n,w;		//n个数，每次push的是w 
    string s;
    cin >>n;
    for(int i = 1;i<=n;i++){
        cin >>s;
        if(s=="push"){	//如果是push 
            cin >> w;
            st.push(w);
            //如果最小栈为空，或push的值≤当前最小栈的栈顶元素 
            if(minst.empty() || w<=minst.top() ){	
                minst.push(w);	//将这个值存入最小栈 
            }
        }else if(s=="pop" && !st.empty()){
        	//如果最小栈的栈顶与即将删除的数相同 
            if(minst.top()==st.top() ){
                minst.pop();	//将最小栈的栈顶也删掉 
            }
            st.pop();	
        }else if(s=="top" && !st.empty()){
            cout << st.top()<<endl;
        }else if(s=="get_min" && !st.empty()){
            cout << minst.top()<<endl;	//最小栈的栈顶是当前最小值 
        }else{
            cout << "error"<<endl;
        }
    }
	return 0;
}