给定两个整数序列 pushV 和 popV,判断 popV 是否可能是 pushV 对应的弹栈序列。解决这个问题的关键在于理解栈'后进先出'的特性。我们可以通过模拟整个压栈和弹栈的过程来验证序列的合法性。
具体做法是使用一个辅助栈和一个指向弹出序列当前位置的指针。遍历压栈序列,将元素依次压入辅助栈。每压入一个元素,就检查栈顶元素是否与弹出序列当前指针指向的元素相同。如果相同,说明可以弹出,于是将栈顶元素弹出,并移动弹出序列的指针。重复此检查直到栈顶不匹配或栈为空。
最后,如果辅助栈为空,说明所有元素都成功按顺序弹出,序列合法;否则不合法。
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
// 使用辅助栈模拟压栈弹栈过程
stack<int> st;
// 双指针:_push 指向当前要压入的元素,_pop 指向当前要弹出的元素
size_t _push = 0; // 压栈序列的索引
size_t _pop = 0; // 弹栈序列的索引
// 遍历所有需要压入的元素
while (_push < pushV.size()) {
// 将当前元素压入栈中
st.push(pushV[_push++]);
// 检查栈顶元素是否与当前期望弹出的元素匹配
// 如果匹配,则连续弹出所有匹配的元素
while (!st.empty() && st.top() == popV[_pop]) {
_pop++; // 移动弹栈序列指针
st.pop(); // 弹出栈顶元素
}
}
// 如果所有元素都能正确弹出,栈应该为空
return st.();
}
};


