14151: 【原4151】出栈序列

题目

题目描述

author: Online Judge 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4151

Description

现在有一个栈, 数字 1-n 按从小到大的顺序入栈. 给你一个出栈序列, 请你判断它是否合法.

Input Format

第一行为一个正整数 T, 表示数据组数;

接下来 T 行, 每行先是一个正整数 n, 紧接着 n 个数表示出栈序列.

Output Format

共 T 行, 每行一个字符串 Yes 或 No, 表示出栈序列是否合法.

Sample Input

2
3 1 3 2
3 3 1 2

Sample Output

Yes
No

Hint

T<=10, n<=10^6

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

int main() {
    int T;
    ios::sync_with_stdio(false);
    cin >> T;

    for (; T > 0; T--) {
        int num;
        bool flag = true;
        cin >> num;
        int stackTop = 0;
        //不断遍历模拟
        for (int i = 0, n = 1; i < num; i++) {
            int currentNum;
            cin >> currentNum;
            if (!flag) continue;
            if (n <= currentNum) {
                stackTop = currentNum;
                n = currentNum + 1;
            }
            if (currentNum <= stackTop)
                stackTop=currentNum;
            else {
                flag = false;
            }
        }

        if (flag)
            printf("Yes\n");
        else
            printf("No\n");

    }


    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

template <class T>
class seqStack {
   private:
    T *data;
    int nowSize;
    int maxSize;
    void doublespace();

   public:
    seqStack(int initSize = 10);
    seqStack(const seqStack<T> &);
    ~seqStack();
    int size() const;
    void push(T);
    T top();
    T pop();
    bool isEmpty();
    T find(T) const;
    seqStack<T> &operator=(const seqStack<T> &);
    T &operator[](int);
};

template <class T>
seqStack<T>::seqStack(int initSize) {
    data = new T[initSize];
    nowSize = 0;
    maxSize = initSize;
}

template <class T>
seqStack<T>::seqStack(const seqStack<T> &right) {
    nowSize = right.nowSize;
    maxSize = right.maxSize;
    data = new T[maxSize];
    for (int i = 0; i < nowSize; i++) {
        data[i] = right.data[i];
    }
}

template <class T>
seqStack<T>::~seqStack() {
    delete[] data;
    data = NULL;
}

template <class T>
void seqStack<T>::doublespace() {
    maxSize *= 2;
    T *tmp;
    tmp = new T[maxSize];

    for (int i = 0; i < nowSize; i++) {
        tmp[i] = data[i];
    }

    delete[] data;
    data = tmp;

    tmp = NULL;
}

template <class T>
int seqStack<T>::size() const {
    return nowSize;
}

template <class T>
void seqStack<T>::push(T x) {
    if (nowSize == maxSize) {
        doublespace();
    }
    data[nowSize++] = x;
}

template <class T>
T seqStack<T>::top() {
    if (nowSize > 0) {
        return data[nowSize - 1];
    }
}

template <class T>
T seqStack<T>::pop() {
    if (nowSize > 0) {
        return data[--nowSize];
    }
}

template <class T>
bool seqStack<T>::isEmpty() {
    return (nowSize == 0);
}

template <class T>
T seqStack<T>::find(T x) const {
    for (int i = 0; i < nowSize; i++) {
        if (data[i] == x) {
            return x;
        }
    }
    return -1;
}

template <class T>
seqStack<T> &seqStack<T>::operator=(const seqStack<T> &right) {
    if (this != &right) {
        delete[] data;

        nowSize = right.nowSize;
        maxSize = right.maxSize;
        data = new T[maxSize];
        for (int i = 0; i < nowSize; i++) {
            data[i] = right.data[i];
        }
    }

    return *this;
}

template <class T>
T &seqStack<T>::operator[](int x) {
    return data[nowSize - x - 1];
}

bool checkOrder(int *a, int n) {
    int save = 0;
    seqStack<int> sta;
    for (int i = 0; i < n; i++) {
        if (a[i] > save + 1) {
            for (int j = save + 1; j < a[i]; j++) {
                sta.push(j);
            }
            save = a[i];
        } else if (a[i] == save + 1) {
            save = a[i];
        } else if (a[i] < save) {
            if (a[i] == sta.top()) {
                sta.pop();
            } else {
                return 0;
            }
        }
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int nums[1000100], T, n;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> nums[j];
        }
        if (checkOrder(nums, n)) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

q4x3's solution

/**
 * 栈模拟
 * 为什么每道题都要快读TATTTTT
 **/
#include <iostream>
#include <stdio.h>

using namespace std;
int tmp, nex, flag = 1;

struct sstack
{
    int a[1000233];
    int top;
};

void read(int &x){
    x = 0;
    char ch;
    while (ch = getchar(), (ch < '0' || ch > '9'));
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = 10 * x + ch - '0';
}

int main() {
    int T;
    cin >> T;
    for(int i = 0;i < T;++ i) {
        int N;
        nex = 0; flag = 1;
        read(N);
        sstack s;
        s.top = 0; s.a[0] = nex;
        for(int i = 0;i < N;++ i) {
            read(tmp);
            while(flag) {
                if(s.a[s.top] == tmp - 1) {
                    -- s.top;
                    break;
                }
                ++ s.top;
                ++ nex;
                if(nex + 1 > N) flag = 0;
                s.a[s.top] = nex;
            }
        }
        if(flag) printf("Yes\n");
        else printf("No\n");
    }
}

victrid's solution

#include <cstdio>
#include <iostream>
using namespace std;
//Changed logic to avoid duplicats.
//NO WA please🙏
int read() {
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x  = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}
int proc[1000000];
int stk[1000000];
int* stkptr = stk;
int T, N, now;
int main() {
    T = read();
    while (T--) {
        N      = read();
        stkptr = stk;
        now    = 0;
        for (int j = 0; j < N; j++)
            proc[j] = read();
        for (int nums = 1; nums <= N; ++nums) {
            *stkptr++ = nums;
            while (stkptr != stk && now < N && proc[now] == stkptr[-1]) {
                stkptr--;
                now++;
            }
        }
        printf(stkptr == stk ? "Yes\n" : "No\n");
    }
    return 0;
}

WashSwang's solution

#include <iostream>
using namespace std;
int t,st[1100000],top,n,now,a[1100000];
int main() {
    ios::sync_with_stdio(false);
    cin>>t;
    for (int i=0;i<t;++i)
    {
        cin>>n;
        now=0;
        top=0;
        for (int j=0;j<n;++j)
            cin>>a[j];
        for (int j=1;j<=n;++j) {
            st[top++] = j;
            while (a[now]==st[top-1]&&now<n&&top>=0) {
                top--;
                now++;
            }
        }
        if (top!=0) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
    return 0;
}