PAT (Advanced Level) Practice 1051 Pop Sequence

比眉伴天荒 2023-07-03 02:38 13阅读 0赞

思路：遍历每个序列，遍历时维护一个值maxn（已遍历过的数中的最大数），maxn初始值为0。  
对于每个数字 i：  
1、若 i 大于maxn，则往栈中push 【maxn+1,i】之间的数（端点值要取），接下来判断是否超出容量，超出则不能构成该序列。

若未超出，则pop栈顶的值（即 i），同时 令maxn=i。

2、若 i 小于maxn，则查看栈顶的值是否等于 i ，不是则不能构成该序列，是则pop栈顶值。

#include <iostream>
    #include <stack>
    #include <vector>
    #include <stdio.h>
    using namespace std;
    int maxin,m,n,k;
    int main()
    {
        cin>>m>>n>>k;
        for(int i=0;i<k;i++){
            vector<int> seq;
            stack<int> st;
            maxin=0;
            for(int j=0;j<n;j++){
                int data;
                scanf("%d",&data);
                seq.push_back(data);
            }
            bool flag=true;
            for(int h=0;h<seq.size();h++){
                if(seq[h] > maxin){
                    for(int i=maxin+1;i<=seq[h];i++){
                        st.push(i);
                    }
                    if(st.size()>m){
                        flag=false;
                        break;
                    }
                    maxin=seq[h];
                    st.pop();
                }else{
                    if(st.top()==seq[h]){
                        st.pop();
                    }else{
                        flag=false;
                        break;
                    }
                }
            }
            if(flag) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        return 0;
    }