Java贪心算法练习-在给定的字符串中删除 m 个字符，使得剩下的字符串的字典序最小

题目描述

给定一个由大写字母组成的长度为 n 的字符串，请在字符串中删除 m 个字符，使得剩下的字符串的字典序最小。

解决方法

你可以使用贪心算法来解决这个问题。具体步骤如下：

1. 从左到右遍历字符串，如果当前字符比前一个字符小，那么就删除前一个字符，并且 m 减 1。重复这一步骤直到 m 为 0 或者遍历完整个字符串。
2. 如果还有剩余的 m，说明字符串中的所有字符都是递增的，此时删除末尾的 m 个字符即可。

下面是一个简单的 Java 实现：

public class Main {
    public static String removeCharsToMinimizeLexicographicOrder(String s, int m) {
        StringBuilder sb = new StringBuilder(s);

        for (int i = 1; i < sb.length() && m > 0; ) {
            if (sb.charAt(i) < sb.charAt(i - 1)) {
                sb.deleteCharAt(i - 1);
                m--;
                if (i > 1) {
                    i--;
                }
            } else {
                i++;
            }
        }

        while (m > 0) {
            sb.deleteCharAt(sb.length() - 1);
            m--;
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        String s = "ZYXWVUTSRQPON";
        int m = 5;
        System.out.println(removeCharsToMinimizeLexicographicOrder(s, m));  // Output: "PON"
    }
}

在这个示例中，removeCharsToMinimizeLexicographicOrder 函数接受一个字符串和一个整数 m，然后返回删除 m 个字符后得到的字典序最小的字符串。希望这个示例对你有所帮助！

运行截图