栈的压入和弹出序列

[题](栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com))

1. 代码

   方法一

   class Solution {
     public:
       bool IsPopOrder(vector<int> pushV, vector<int> popV) {
           stack<int> stack;
           int j = 0, n = pushV.size();
           for (const auto& item : popV) {
               while (j < n && (stack.empty() || stack.top() != item)) {
                   stack.push(pushV[j++]);
               }
               if (stack.top() == item) {
                   stack.pop();
               } else {
                   return false;
               }
           }
           return true;
       }
   };

   方法二（自写）

   class Solution {
     public:
       bool IsPopOrder(vector<int> pushV, vector<int> popV) {
           if (pushV.size() != popV.size()) {
               return false;
           }
           for (int i = 0, j = 0; i < pushV.size(); i++) {
               while (i < pushV.size() &&i >= 0&& pushV[i] == popV[j] ) {
                   pushV.erase(pushV.begin() + i);
                   i--;
                   j++;
               }
               if (popV.size() == j) {
                   return true;
               }
           }
           return false;
       }
   };

2. 提示

   方法一：

   

   方法二：

   1. 遍历push，如果当发现push的元素与pop的元素相等的话，我们就选择将这个push元素erase,并且将下标往前移动一，也就是i--
   2. 如果发现pop也都遍历完了，我们就return成功。如果push的下标超过了push.size()我们就选择return false

3. 理解

   方法一

   • 确保push遍历完时，还可以遍历pop，所以采取遍历pop的方式

   • 借助辅助栈，对比是否出栈的顺序是否一致

   • 整体的思路如下

     当push没有遍历完，且栈是空或者栈顶不和pop一致，应该往栈push

     如果发现栈顶的值与pop的一致，应该跳出循环，并将栈顶的元素弹出

     如果当push走完时，栈顶元素不和pop相等则说明不相等

   • 当两个vector都遍历完时，则说明序列一致

   方法二

   • 将push拿来遍历，如果push都走完了，我们的pop还没走完就选择return false
   • 如果size都不相等，就像应该直接返回false

4. 问题

   方法一

   • 如何确保push完全走完

     循环遍历pop

   方法二

   • 如何防止popV越界

     使用i>=0，如果该条件不满足，则说明已经遍历完成