最小栈

题解：

考察点： 栈

易错点：

本题要求、、三种操作都在复杂度内完成，也就是说都必须在常数时间内完成，其中和都是栈本来的操作，很多同学会考虑使用堆来维护最小值，但是这是不对的，因为堆每次找最小值的时间复杂度为

题解：

可以考虑使用两个栈来共同维护，一个栈用来进行元素常规的出栈和入栈操作，另一个栈维护最小值，其中栈顶元素表示当前栈中的最小值。对于入栈操作，首先将入栈，如果比中的栈顶元素小，或者为空，则将加入中。对于操作，直接取栈中的栈顶元素。对于出栈操作，栈直接出栈，如果当前栈顶元素等于的栈顶元素，则把的栈顶出栈

#include "bits/stdc++.h"
using namespace std;
stack<int>s;
stack<int>Min;
void Push(int x){
    s.push(x);
    if(Min.empty()) Min.push(x);
    else{
        int tmp=Min.top();
        if(x<=tmp) Min.push(x);
    }
}
int GetMin(){
    return Min.top();
}
int Pop(){
    int tmp=s.top(); s.pop();
    if(tmp==Min.top()&&!Min.empty()) Min.pop();
    return tmp;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int op;
        scanf("%d",&op);
        if(op==0){
            printf("%d\n",GetMin());
        }else if(op==1){
            int x; scanf("%d",&x);
            Push(x);
        }else{
            printf("%d\n",Pop());
        }
    }
    return 0;
}