思路:题目给出了两个整型元素的顺序表,一个是入栈顺序,一个是出栈顺序,我们创建一个栈,通过某种算法来模拟入栈和出栈的过程,如果创建的栈中最后不存在元素,说明出栈顺序是正确的。
class Solution
{
public:bool IsPopOrder(vector<int> pushV, vector<int> popV) {//创建一个新的栈stack<int> ret;//标识出栈到出栈序列的第几个元素size_t popCur = 0;//记录顺序表的大小,避免后续重复调用size()函数。size_t pushSize = pushV.size();size_t popSize = popV.size();//将入栈序列依次入栈到ret中for(int i=0; i<pushSize; ++i){ret.push(pushV[i]);//如果ret栈顶的元素和popV当前遍历到的元素一样,ret就出栈,再依次比较popV的下一个元素.//对于迭代遍历的情况,需要考虑边界条件(取栈顶要求栈中有元素,访问数组元素要求在数组范围内)。while(!ret.empty() && popCur < popSize && ret.top() == popV[popCur]){ret.pop();popCur++;}}return ret.empty();}
};