问题描述
给定两个整数序列:pushV(压栈序列)和 popV(待验证的弹栈序列)。我们需要判断 popV 是否可能是 pushV 对应的合法弹栈序列。
核心思路
解决这个问题的关键在于理解栈的后进先出特性。我们可以通过模拟整个压栈和弹栈的过程来验证序列的合法性。
具体策略如下:
- 压栈操作:元素按照
pushV的顺序依次入栈。 - 弹栈操作:在任意时刻,如果栈顶元素与当前期望弹出的元素匹配,则立即弹出。
- 贪心选择:只要栈顶能匹配,就立刻弹出,因为如果不现在弹出,后续再想弹出它就必须先把上面的元素压进去,这会导致顺序错乱。
代码实现
下面是一个基于 C++ STL 的实现,利用辅助栈和双指针来跟踪进度。
#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.();
}
}
st.();
}
};


