【剑指Offer】T31 栈的压入、弹出序列

给定 pushV 和 popV 两个序列,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。

输入:pushV = [1,2,3,4,5], popV = [4,5,3,2,1]
输出:true
解释:我们可以按以下顺序执行:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

输入:pushV = [1,2,3,4,5], popV = [4,3,5,1,2]
输出:false
解释:1 不能在 2 之前弹出。

思路:

  • popupopVpushV的指针
  • 外层循环:指针停留在 popV,比较 popV[pop]和栈内元素
    • 栈空:入栈元素,pu++
    • 栈顶 != popV[pop]:入栈,pu++
      • pu == len,即pu移动到了范围外,还在本循环内,return false;
    • 栈顶 == popV[pop] :出栈、po++;
      • 数组走完,出循环,都比较完,return true;(因为退出条件是在栈状态和popV决定,绝对严格,有不符合就会退出,所以可以保证最后popV循环完,一定都匹配)
  bool IsPopOrder(vector<int> pushV,vector<int> popV) {
      int len = pushV.size();
      if(len == 0)
          return true;
      if(len == 1)
          return pushV[0] == popV[0] ? true : false;
  
      stack<int> stk;
  
      int pu = 1, po = 0; // pushV 和 popV的游标
      while(po <= len-1){
          if(stk.empty()){
              stk.push(pushV[pu]);
              pu++;
          }
  
          while(stk.top() != popV[po]){
              // 栈顶不等于带比较元素,且指针移动到了最后
              if(pu == len)
                  return false;
              // 不匹配时,入栈
              stk.push(pushV[pu]);
              pu++;
          }
          // 匹配,出栈,popV前移
          stk.pop();
          po++;
      }
      // popV一直比较到了末尾
      return true;
  }

本文链接:https://ariser.cn/index.php/archives/370/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!