牛客網棧的壓入,和彈出序列

• 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;        }  };