描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
-
0 <= pushV.length == popV.length <= 1000
-
-1000 <= pushV[i] <= 1000
-
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 思路：
使用栈的入栈和出栈来模拟这个出栈顺序：
- 如果能模拟出来说明就是正确的
- 反之则不成立
步骤：
- 先把 pushV 数组中的值入栈
- popV 数组中的值依次和跟栈里面的数组进行比较，若相同，则说明在此处进行 pop 掉栈中的数据，也就是让 popV 数组的下标向后走，不断出栈里的数据，直到栈为空或数值不相同则将 pushV 元素向后走，继续入栈。
- 结束条件是 pushV 数组已经遍历完
- 最后判断一下：
- 如果 popV 数组走完了，说明是匹配的
- 如果 popV 数组没走完，说明是不匹配的
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> st;
size_t popIndex = 0;
for(size_t i = 0; i < pushV.size(); ++i)
{
st.push(pushV[i]);
// 若栈为空或者栈顶数据与popV[j]元素不同则退出循环
// 注意：这里判空要放在前面，不然先判断popV[j]可能导致越界
while((!st.empty()) && (st.top() == popV[popIndex]))
{
st.pop();
popIndex++;
// 如果popV走完了，说明序列是对的了
if(popIndex >= popV.size())
return true;
}
}
// 判断剩余的是否符合
while(!st.empty())
{
if(st.top() != popV[popIndex])
return false;
popIndex++;
st.pop();
}
// 走完pushV后，popV走完，说明序列是对的
return true;
}
}; 另一种简约写法：
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> st;
int popIndex = 0;
for(int i = 0; i < pushed.size(); ++i)
{
st.push(pushed[i]);
while(!st.empty() && st.top() == popped[popIndex])
{
popIndex++;
st.pop();
}
}
// 若st还不为空说明不匹配，z
return st.empty();
}
};