本题出处—最小栈_牛客网
题目描述 实现一个最小栈，有三种操作，min：得到栈中的最小值，push：在栈顶插入一个元素，pop：弹出栈顶元素，使这三种操作的时间复杂度都是O(1)
输入描述:
第一行是一个数Q，接下来Q行每行表示一个操作，每行首先是操作op 若op=0,则输出当前栈中的最小值； 若op=1，表示push，接着正整数x，把在x放进栈顶； 若op=2，表示pop，弹出栈顶元素 保证Q<=500000,保证op=0或2时（即min操作和pop操作时）栈不为空。 你可以假设一开始栈的空的。
输出描述:
对应每个op=0或2，如果是op=0输出当前栈中的最小值，如果是op==2输出弹出的元素。
示例1
输入
7 1 3 1 4 0 1 2 0 2 0
输出
3 2 2 3
说明
第一个操作为push 3,此时栈元素为3 第二个操作为push 4,此时栈元素为3,4 第三个操作为min,此时栈元素为3,4，输出最小值3 第四个操作为push 2,此时栈元素为3,4,2 第五个操作为min,此时栈元素为3,4,2，输出最小值2 第六个操作为pop,弹出元素2，此时栈元素为3,4，输出弹出的元素2 第七个操作为min,此时栈元素为3,4，输出最小值3
首先想到的是创建两个栈，一个用来存放数据，一个用来存放最小元素
#include <iostream> #include <stack> #include <algorithm> using namespace std; stack<int> stackData; stack<int> stackMin; int main() { int Q, op, x; cin >> Q; while (Q--) { cin >> op; if (op == 1) { cin >> x; stackData.push(x); if (!stackMin.empty()) stackMin.push(min(stackMin.top(), x)); else stackMin.push(x); } else if (op == 2) { cout << stackData.top() << endl; stackData.pop(); stackMin.pop(); } else { cout << stackMin.top() << endl; } } return 0; }用下面代码就通过了
#include <iostream> #include <stack> #include <algorithm> #include <cstdio> using namespace std; stack<int> stackData; stack<int> stackMin; int main() { int Q, op, x; scanf("%d",&Q); while (Q--) { scanf("%d",&op); if (op == 1) { scanf("%d",&x); stackData.push(x); if (!stackMin.empty()) stackMin.push(min(stackMin.top(), x)); else stackMin.push(x); } else if (op == 2) { printf("%d\n",stackData.top()); stackData.pop(); stackMin.pop(); } else { printf("%d\n",stackMin.top()); } } return 0; }cin，cout比printf，scanf效率要低。
