剑指 Offer 31. 栈的压入、弹出序列

我写的笨比代码

使用标记加哈希，无论是时间复杂度还是空间复杂度都很差

  1. class Solution {
  2. public:
  3.     bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
  4.         int n = pushed.size(), cur = 0, pre = 0;
  5.         unordered_map<int, int> hash;
  6.         vector<int> flags(n+1);
  7.         for(int i = 0; i < n; i++){
  8.             hash[pushed[i]] = i;
  9.         }
  10.         for(int i = 0; i < n; i++){
  11.             cur = hash[popped[i]];
  12.             for(int k = cur + 1; k < n; k++){
  13.                 if(flags[k] == 1) return false;
  14.             }
  15.             flags[cur] = 2;
  16.             if(cur > pre){
  17.                 for(int j = 0; j < cur; j++){
  18.                     if(flags[j] == 0){
  19.                         flags[j] = 1;
  20.                     }
  21.                 }
  22.             }
  23.             pre = max(cur, pre);
  24.         }
  25.         return true;
  26.     }
  27. };

直接使用模拟的方法来写

  1. class Solution {
  2. public:
  3.     bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
  4.     stack<int> st;
  5.     for (int i = 0, j = 0; i < popped.size(); i++) {
  6.         while ((st.empty() || st.top() != popped[i]) && j < pushed.size()) {
  7.             st.push(pushed[j++]);
  8.         }
  9.         if (popped[i] == st.top()) st.pop();
  10.     }
  11.     return st.empty();
  12.     }
  13. };