第十五届蓝桥杯模拟赛 -- 删掉m个字符使得字典序最小

第十五届蓝桥杯模拟赛 -- 删掉m个字符使得字典序最小

贪心 + 单调栈

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String[] strings = scanner.nextLine().split(" ");
		int n = Integer.parseInt(strings[0]);
		int m = Integer.parseInt(strings[1]);
		String string = scanner.nextLine();
		
		Deque<Character> deque = new LinkedList<>();
		for (int i = 0; i < string.length(); i ++) {
			while (!deque.isEmpty() && m > 0 && deque.peekLast() > string.charAt(i)) {
				m --;
				deque.pollLast();
			}
			deque.offer(string.charAt(i));
		}
		
		while (m > 0) {
			deque.pollLast();
			m --;
		}
		
		StringBuilder sBuilder = new StringBuilder();
		while (deque.size() > 0) {
			sBuilder.append(deque.pollFirst());
		}
		System.out.println(sBuilder);
	}
}

相关题目: leetcode 402.移掉k位数字