贪心算法 —— 字典序删除字符

题目描述

���定一个单词，请问在单词删除t个字母之后，能得到的字典序最小的单词是什么？

（）

输入描述

输入的第一行包含一个单词，有大写英文字母组成

第二行包含一个正整数t

（）

其中，单词长度不超过100，t小于单词长度

输出描述

输出一个单词，表示答案

输入输出样例

LANQIAO
3

输出

AIAO

题解

本题是一道经典的贪心算法的问题。我们要做的就是找到局部最优解，从而获得全局最优解。

首先，什么是字典序最小的排列呢？显然就是在顺序不变的情况下，将小的字符往前排。最终得到的排列一定会是从小到大的阶梯状排序。因此，我们要做的就是每次都从头遍历字符串，将那些升序排列中的“不和谐因素”逐一删除。当然，因为是从头遍历，因此字典序将会是最小。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String word = scan.next();
        int t = scan.nextInt();
        StringBuilder result = new StringBuilder(word);
        for (int i = 0; i