题目描述
给定两个整数序列：
pushV：压栈序列popV：待验证的弹栈序列
需要判断 popV 是否可能是 pushV 对应的合法弹栈序列。
核心思路
要解决这个问题，关键在于理解栈的后进先出（LIFO）特性。我们需要模拟整个压栈和弹栈的过程：
- 压栈操作：元素按照
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.empty();
}
};
执行过程模拟
让我们通过一个具体例子来理解算法的执行逻辑：
示例输入：
pushV = [1, 2, 3, 4, 5]popV = [4, 5, 3, 2, 1]
初始状态：栈为空，_push 指向 1，_pop 指向 4。
首先，我们按顺序压入元素 1、2、3。此时栈内为 [1, 2, 3]，栈顶是 3，不等于目标值 4，继续压入。
压入 4 后，栈变为 [1, 2, 3, 4]。发现栈顶 4 与目标值 4 匹配，于是弹出 4，_pop 移动到 5。此时栈顶是 3，不匹配 5，继续压入。
压入 5 后，栈变为 [1, 2, 3, 5]。栈顶 5 匹配目标值 5，弹出 5，_pop 移动到 3。接着栈顶 3 匹配 3，弹出；栈顶 2 匹配 2，弹出；栈顶 1 匹配 1，弹出。
最终栈为空，说明序列合法，返回 true。
复杂度分析
时间复杂度
主循环遍历 pushV 中的每个元素一次。虽然内部有一个嵌套的 while 循环用于弹出元素，但每个元素最多被压入一次、弹出一次。因此，整体操作次数与序列长度 n 成正比，时间复杂度为 O(n)。
空间复杂度
需要一个辅助栈 st 来存储元素。最坏情况下（例如全部压入后才开始弹出），栈中会存储所有 n 个元素。因此，空间复杂度为 O(n)。
边界情况处理
在实际编码中，还需要考虑一些特殊场景：
- 空序列：如果两个序列都为空，通常视为合法匹配。
- 长度不一致：如果
pushV和popV长度不同，直接判定为非法。 - 单元素序列：单个元素的匹配逻辑同样适用上述通用流程。
总结
这道题是考察栈特性的经典案例。通过引入辅助栈进行模拟，配合双指针技巧，我们可以高效地验证序列合法性。掌握这种'模拟 + 贪心'的思维方式，对于解决其他数据结构相关的算法问题也很有帮助。
