Early Orders单调栈

链接

题目描述

You are given a list of integers n and a number k.

It is guaranteed that each i from 1 to k appears in the list at least once.

Find the lexicographically smallest subsequence of x that contains

each integer from 1 to k exactly once.

输入描述:

输出描述:

Write out on one line, separated by spaces, the lexicographically smallest

subsequence of x that has each integer from 1 to k exactly once.

示例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

大体思路：

用pos数组来记录每个数出现的最后的位置

然后遍历每一个数组元素，如果当前元素已经被标记过了（已经被使用），那么就跳过这次循环

设遍历数组元素的时候，将这个数组的下标记为 i ,值的大小为 x

当栈里面有元素，并且栈顶的元素大于x，并且栈顶这个数最后出现的位置大于当前这个数最后出现的位置 i ,那么说明栈里面这一数列就不是最优的，就可以将当前的元素x替换掉栈顶元素，先pop(),然后将这个数标记为 0 ，–>未使用

如果当上述条件一直满足的时候，可以一直进行上面的操作

知道不满足题意，然后讲当前这个数放到栈的顶端

得到的数列一定是与答案相反的，如果是用数组模拟，可以直接按照顺序输出前面的m个元素

如果使用STL，可以再开一个栈倒置一下，然后输出前面的m个元素，即为答案

细节：用stl封装的栈在取用栈顶端的元素的时候应该考虑到当前栈是不是有元素，否则会报错

用数组模拟栈的时候，要考虑到数组下标的问题，否则也会导致出错

关于为什么要考虑到站定这个数最后出现的位置大于当前这个数最后出现的位置 : ->因为满足这个条件的时候，后面的元素还有机会再次进入栈中（后面还会出现这个数，还能进入栈），否则没有机会进入栈中会影响答案

int n,m;
stack<int> st;
int a[maxn];
int pos[maxn];
map<int,bool> mp;
int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        a[i] = read;
        pos[a[i]] = i;
    }
    for(int i=1;i<=n;i++){
        if(mp[a[i]]) continue;
        while(st.size() && st.top() > a[i] && pos[st.top()] > i) {
            int tp = st.top();
            st.pop();
            mp[tp] = 0;
        }
        st.push(a[i]);
        mp[a[i]] = 1;
    }
    stack<int> st2;
    while(st.size()){
        st2.push(st.top());
        st.pop();
    }
    for(int i=1;i<=m;i++){
        printf("%d ",st2.top());
        st2.pop();
    }
    return 0;
}