PAT甲级1051Pop Sequence

Posted on | | Visitors:
Words count in article: 379 字 | Reading time ≈ 2 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805427332562944

题解

题目要求

  • 背景

    给定一个最大容量为M的栈，随机压入和弹出N个数(从1到N)。请判断一个序列是否有可能是该栈弹出的序列

  • 输入

    • M：不超过1000，栈的最大容量
    • N：不超过1000，输入序列的长度
    • K：不超过1000，待检查的序列的数量
    • K个序列

解题思路

模拟入栈和出栈的过程，参考了柳婼的题解。

从1到N入栈：每入栈一个数字，便判断是否出栈，如果可以出栈则出栈（重复此步骤）。如果入栈后，栈大小超过M，则跳出循环停止入栈，结果为NO；如果正确模拟了入栈和出栈，则结果为YES。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Problem: PAT Advanced 1051
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805427332562944
// Tags: 栈

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main()
{
    int m, n, k;
    scanf("%d%d%d", &m, &n, &k);
    vector<int> v(n + 1);
    
    while (k--){
        for (int i = 1; i <= n; i++)
            scanf("%d", &v[i]);

        stack<int> s;
        int current = 1;
        for (int i = 1; i <= n; i++){
            s.push(i);
            if (s.size() > m)
                break;
            while (!s.empty() && s.top() == v[current]){
                s.pop();
                current++;
            }
        }

        if (current == n + 1)
            printf("YES\n");
        else
            printf("NO\n");        
    }
    return 0;
}

参考链接

https://blog.csdn.net/liuchuo/article/details/52215337

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!