牛客网栈的压入,和弹出序列

• 2019 年 10 月 17 日
• 筆記

题目描述如下：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解决思路

用栈的数据结构，

1. 首先根据栈的弹出序列，判断，弹出序列中的元素，是否入栈，
2. 如果没入栈的话，需要将该元素，在压入序列中进行查找，在压入序列中该元素的之前的元素都需要入栈。
3. 如果栈顶元素与弹出序列的元素相同的话，删除栈顶元素。

合法的弹出序列判别条件为：

1. 弹出序列已经完全与栈顶元素匹配过
2. 栈中的元素为空

实现的代码为：

class Solution {    public:      bool IsPopOrder(vector < int >pushV, vector < int >popV) {      stack < int >sta;       set < int >numSet;      // int *num;      int len = popV.size();      // num = new int[len];      // memset(num,0,sizeof(int)*len);      int i = 0;      while (i < len) {            if (numSet.find(popV[i]) == numSet.end()) {          for (int j = 0; j < len; j++) {              if (numSet.find(pushV[j]) == numSet.end()) {              sta.push(pushV[j]);              numSet.insert(pushV[j]);              }              if (pushV[j] == popV[i]) {              break;              }          }          }          if (!sta.empty()) {          int temp = sta.top();          if (temp == popV[i]) {              sta.pop();              i++;          } else {              break;          }            }        }      if (i == len && sta.empty()) {          return true;      }      return false;        }  };