摘要
Title: 1535. 弹出序列
Tag: 栈
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1535. 弹出序列

• 题意

  给定一个最多能存 M 个数字的栈，将 1∼N 按顺序压入栈中，过程中可随机弹出栈顶元素。
  当 N 个数字都经历过入栈和出栈后，我们按照元素出栈的顺序，可以得到一个弹出序列。
  现在给定一系列 1∼N 的随机排列序列，请你判断哪些序列可能是该栈的弹出序列。
  例如，当 N=7,M=5 时，1, 2, 3, 4, 5, 6, 7可能是该栈的弹出序列，而 3, 2, 1, 7, 5, 6, 4 不可能是该栈的弹出序列。

• 思路

  模拟弹栈和入栈过程即可

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-05-12 20:04:45
  * @Last Modified by:   NEFU AB-IN
  * @Last Modified time: 2022-05-12 20:04:45
  */
  #include <bits/stdc++.h>
  #define SZ(X) ((int)X.size())
  
  using namespace std;
  
  int main()
  {
      int m, n, k;
      cin >> m >> n >> k;
      for (int _ = 1; _ <= k; ++_)
      {
          vector<int> a(n);
          for (int i = 0; i < n; ++i)
          {
              cin >> a[i];
          }
          stack<int> s;
          int cnt = 1;  // 需要push进去的元素
          int id = 0;   // 判断序列的指针
          int flag = 1; // 是否成立
          while (cnt < n + 1)
          {
              s.push(cnt++);
              if (SZ(s) > m)
              {
                  flag = 0;
                  break;
              }
              while (SZ(s) && s.top() == a[id])
              {
                  id++;
                  s.pop();
              }
          }
          if (flag && !SZ(s))
              cout << "YES\n";
          else
              cout << "NO\n";
      }
      return 0;
  }