题目链接

题意

给出一个长度为n的数组，每次操作都要删除数组里面非递增的元素，问最终的数组元素有什么。

思路

容易想到用链表模拟删除，但是不能每次都暴力枚举，这样复杂度O（N^2）。想到每次删除元素的时候只会影响前后，因此考虑从前面一个位置开始检查，而不用每次都扫一遍。每次check的时候，发现了不符合题意的情况要把前面的数或者后面的数一起放进vector等待删除。然后删除vector里面把每次删除的数的前面放进一个队列，这个队列里面的值就是等待check的，而且用一个标记数组记录删除了哪些元素，这样就不用每次都扫重复的值了。复杂度接近O（n）。注意输出格式，每个数后面都有空格。

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5 + 10;

typedef long long LL;

int a[N], pre[N], nxt[N], vis[N];

vector<int> mark, ans;

queue<int> que;

void solve() {

    for(int i = 0; i < mark.size(); i++) {

        int k = mark[i];

        if(vis[k]) continue;

        vis[k] = 1;

        que.push(pre[k]);

        pre[nxt[k]] = pre[k];

        nxt[pre[k]] = nxt[k];

    }

}

void del(int i) {

    if(a[pre[i]] > a[i]) {

        mark.push_back(i);

        mark.push_back(pre[i]);

    }

    if(a[nxt[i]] < a[i]) {

        mark.push_back(i);

        mark.push_back(nxt[i]);

    }

}

int main() {

    int t; scanf("%d", &t);

    while(t--) {

        int n; scanf("%d", &n);

        while(!que.empty()) que.pop();

        a[0] = 0; a[n+1] = 0x3f3f3f3f;

        pre[n+1] = n; nxt[0] = 1;

        for(int i = 1; i <= n; i++) {

            scanf("%d", &a[i]);

            vis[i] = 0;

            nxt[i] = i + 1;

            pre[i] = i - 1;

            que.push(i);

        }

        while(1) {

            mark.clear();

            while(!que.empty()) {

                int u = que.front(); que.pop();

                del(u);

            }

            if(!mark.size()) break;

            solve();

        }

        ans.clear();

        int cnt = 0;

        for(int i = 0; i <= n; i = nxt[i]) {

            if(a[i] == 0) continue;

            cnt++; ans.push_back(a[i]);

        }

        if(!cnt) puts("0\n");

        else {

            printf("%d\n", cnt);

            for(int i = 0; i < ans.size(); i++) {

                printf("%d ", ans[i]);

            } puts("");

        }

    }

    return 0;

}