题解 | #删除字符#

如何实现字符串的字典序最小?

• 答:小字母放前面.

对于这一组用例来说

10 4
lkqijxsnny

需要保留6个字符,那么也就意味着需要从lkqij中选出第一个字符(因为剩下的xsnny只有5个字符,如果从其中选第一个的话,总数就不够6个了)

显然需要选i,因为字典序的比较是从左到右一个一个比较,如果第一个就小的话,那么后边就不用比了;这里如果用其他字符做第一个字母,那么已经输给i开头的字符串了.

lkqijxsnny

首先从lkqij中选出第一个字符,此时选中i

jxsnny

然后需要从jx中选出第二个字符,此时选中j

xsnny

然后需要从xs中选择第三个字符,此时选中s

nny

然后需要从n中选择第四个字符,此时选中n

ny

然后需要从n中选择第五个字符,此时选中n

y

然后需要从y中选择第六个字符,此时选中y

最后的结果是ijsnny

这个过程可以用单调队列来处理(凡是在我左边还比我小的字符,通通出队)

import java.util.*;
public class Main{

    String str;

    void solve(){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t>0){
            t--;
            int n=sc.nextInt();
            int m=n-sc.nextInt();    //保留多少个数字
            str=sc.next();
            //单调队列-用双端队列来实现
            Deque<Character>incQue=new ArrayDeque<>();
            for(int i=0;i<=n-m-1;i++){
                while(!incQue.isEmpty() && str.charAt(i)<incQue.peekLast())
                    incQue.pollLast();
                incQue.offer(str.charAt(i));
            }
            List<Character>ans=new ArrayList<>();
            for(int i=n-m;i<n;i++){
                while(!incQue.isEmpty() && str.charAt(i)<incQue.peekLast())
                    incQue.pollLast();
                incQue.offer(str.charAt(i));
                ans.add(incQue.poll());
            }
            for(int i=0;i<ans.size();i++)
                System.out.print(ans.get(i));
            System.out.println();
        }
    }

    public static void main(String[]args){
        new Main().solve();
    }
}