如何实现字符串的字典序最小?
- 答:小字母放前面.
对于这一组用例来说
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();
}
}