目录
最小栈
思路
编辑
实现
栈的压入、弹出序列
思路
实现
需要注意的
最小栈
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
设计一个支持 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.思路
这道题的难点有两个，一是理解题意，它不是让我们去模拟实现库里的stack，所以我们可以直接用库里的stack及其接口。
（不要像我一开始拿到题，以为是要模拟实现栈的几个接口，哐哐就开整了。。。）
二是在常数时间内实现“getMin() ：获取堆栈中的最小元素”。难在时间复杂度上。
但没关系，有句话叫“用空间换取时间”，这道题就用这个思路解决。
我们在类MinStack里 实例化出两个对象：普通栈st、“越来越小栈”min_st。
数据会直接插入st，却未必能插入min_st。只有比栈顶更小的，才能插入min_st。
实现
class MinStack {
public:
stack<int> st;
stack<int> min_st;
MinStack()
{}
void push(int val) {
st.push(val);
if(min_st.empty()||val<=min_st.top()){ //<=
min_st.push(val);
}
}
void pop() {
if(st.top()==min_st.top()){
min_st.pop();
}
st.pop();
}
int top() {
return st.top();
}
int getMin() {
return min_st.top();
}
};栈的压入、弹出序列
栈的压入、弹出序列_牛客题霸_牛客网
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1.0<=pushV.length == popV.length <=1000
2.-1000<=pushV[i]<=1000
3.pushV 的所有数字均不相同
示例1
输入：[1,2,3,4,5],[4,5,3,2,1]
返回值：true
说明：可以通过
push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true 示例2
输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false
说明：由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false思路
首先我们要明白一件事：栈的元素是可以在中途弹出的，比如[1,2,3,4,5]，它的弹出顺序也可以是[1,2,3,4,5]：把1压入再弹出，再把2压入弹出，把3压入弹出……
而[4,3,5,1,2]就不行，我们模拟一下入栈、出栈的顺序就会发现，2一定是在1之前出栈的。
所以这道题，我们要做的就是：实例化一个栈，模拟入栈、出栈的过程。
实现
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
stack<int> st;
int pushi=0,popi=0;
while(pushi<pushV.size()){
st.push(pushV[pushi]);
pushi++;
while(!st.empty()
&& popV[popi]==st.top()){
st.pop();
popi++;
}
}
return st.empty();
}
};需要注意的
1.当栈为空时，不要取栈顶数据！会报错
一开始我是这么写的，当测试用例为[2,1,0],[1,2,0]时，程序报段错误。看看错误出在哪：
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
stack<int> st;
int pushi = 0, popi = 0;
while (pushi < pushV.size()) {
st.push(pushV[pushi]);
pushi++;
while (popi < popV.size()
&& popV[popi] == st.top()) {
st.pop();
popi++;
}
}
return st.empty();
}
};错误就出在那个小while循环的判断条件里：
while (popi < popV.size()
&& popV[popi] == st.top()) {
……
}最后栈删空了，经过这个循环，会在循环条件里做一个判断，此时调用top()函数，就出问题了。
所以，判断条件应为：
while (!st.empty()
&& popV[popi] == st.top()) {
……
}所以，当取栈顶数据时，一定要加个判空的前置条件！
