E-Early Orders 题解

链接：https://ac.nowcoder.com/acm/contest/12606/E
来源：牛客网

示例1
输入
6 3
3
2
1
3
1
3

输出
2 1 3

示例2
输入
10 5
5
4
3
2
1
4
1
1
5
5

输出
3 2 1 4 5

#include<bits/stdc++.h>
using namespace std;

#define MAXN 200005
int x[MAXN] = { 0 };
int js[MAXN] = { 0 };
bool in_stack[MAXN] = { false };

int main()
{
    int k, n;
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &x[i]);
        js[x[i]]++;
    }

    stack<int> s;
    s.push(x[0]);
    js[x[0]]--;
    in_stack[x[0]] = true;

    for (int i = 1; i < n; ++i)
    {
        js[x[i]]--;
        //if(x[i]==1) cout<<"aaa"<<in_stack[1]<<endl;
        while (!s.empty() && (s.top() > x[i]) && (js[s.top()] > 0) && in_stack[x[i]] == false)
        {
            in_stack[s.top()] = false;
            s.pop();
        }
        if (in_stack[x[i]] == false)
        {
            s.push(x[i]);
            in_stack[x[i]] = true;
            //cout<<x[i]<<' '<<in_stack[x[i]]<<endl;
        }

    }
    list<int> li;

    while (!s.empty())
    {
        li.push_front(s.top());
        s.pop();
    }

    while (!li.empty())
    {
        printf("%d", li.front());

        if (li.size() > 1)
            printf(" ");
        else printf("\n");


        li.pop_front();
    }
    //system("pause");
}