Zhao70's Blog

Pop Sequence

发表于 | 分类于

题目大意

给定栈的大小m， 序列长度n， 和测试数据的个数k
每一组序列的入栈顺序都为 1 - n, 求每组出栈顺序能否成立。

思路

对于每一组序列， 入栈次序都为 1 - n， 而出栈次序已经给出， 我们只需要一次入栈， 当栈顶元素为序列中的一个元素时即出栈， 模拟看是否能够实现。
设置cur变量指向序列中元素， 循环进行1 - n的压栈操作， 当遇到cur指向的元素与栈顶元素相等即出栈， 直至不相等。

代码

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
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main()
{
    int sizeOfStack, lenSeq, nSeq;
    cin >> sizeOfStack >> lenSeq >> nSeq;
    for(int k = 0; k < nSeq; k++)
    {
        vector<int> seq(lenSeq + 1);
        stack<int> st;
        bool flag = false;
        for(int i = 1; i <= lenSeq; i++)
            cin >> seq[i];
        int cur = 1;
        for(int i = 1; i <= lenSeq; i++)
        {
            st.push(i);
            if(st.size() > sizeOfStack)
                break;
            while(st.empty() == false && seq[cur] == st.top() )
            {
                //cout << st.top();
                st.pop();
                cur++;
            }
        }
        if(cur == lenSeq + 1)
            flag = true;
        if(flag) cout << "YES" << endl;
        else    cout << "NO" << endl;
    }
    return 0;
}