问题描述
给定两个整数序列：
pushV：压栈序列popV：待验证的弹栈序列
需要判断 popV 是否可能是 pushV 对应的弹栈序列。
核心思路
要解决这个问题，关键在于理解栈的后进先出特性。我们可以通过模拟整个压栈弹栈过程来验证序列的合法性。
具体规则如下：
- 压栈操作：元素按照
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++]);
// 检查栈顶元素是否与当前期望弹出的元素匹配
// 如果匹配，则连续弹出所有匹配的元素
(!st.() && st.() == popV[_pop]) {
_pop++;
st.();
}
}
st.();
}
};
