3.1 综合题：用一个栈验证另一个序列

给定入栈序列 pushSeq 与候选出栈序列 popSeq，可以用模拟栈在线性时间验证。逐个读入元素并入栈；只要栈顶等于当前待输出元素，就持续弹出并推进输出指针。最后输出指针到达末尾才合法。

bool valid(const vector<int>& in,const vector<int>& out){
  if(in.size()!=out.size()) return false;
  vector<int> st; size_t j=0;
  for(int x:in){
    st.push_back(x);
    while(!st.empty()&&j<out.size()&&st.back()==out[j]){
      st.pop_back(); ++j;
    }
  }
  return j==out.size();
}

循环不变量：处理完输入前缀后，已输出部分与候选序列前缀一致，栈中保留尚未输出且被后入元素阻挡的元素。每个元素恰好入栈、出栈一次，时间 $O(n)$，辅助空间 $O(n)$。

手工推演 in=[1,2,3,4]、out=[2,4,3,1]：入 1 无法出；入 2 后出 2；入 3；入 4 后依次出 4、3；最后出 1，合法。对 out=[3,1,4,2]，出 3 后栈顶 2 与目标 1 不同，后续再入 4 也无法移开 2，最终失败。

错解反馈：只在每次入栈后弹一次，会漏掉连续可弹出的多个元素；不检查长度相同，可能把候选前缀误判为合法；用搜索或回溯枚举所有操作路径是指数级浪费，因为贪心模拟在目标确定时没有选择歧义。

迁移练习：扩展函数，让它在失败时返回第一个无法匹配的输出下标及当时栈内容。独立验收：至少通过空序列、单元素、全逆序、一个不合法序列四组测试，并解释不变量。