【LeetCode】3170. 删除星号以后字典序最小的字符串（贪心 | 优先队列）

题目描述

题目链接：3170. 删除星号以后字典序最小的字符串

给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。

当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：

• 删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。

请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。

示例1：

输入：s = “aaba*”
输出：“aab”
解释：删除 ‘*’ 号和它左边的其中一个 ‘a’ 字符。如果我们选择删除 s[3] ，s 字典序最小。

示例 2：

输入：s = “abc”
输出：“abc”
解释：字符串中没有 ‘*’ 字符。

提示：

• 1 <= s.length <= $10^5$
• s 只含有小写英文字母和 ‘*’ 字符。
• 输入保证操作可以删除所有的 ‘*’ 字符。

解题思路

• 题目剖析：

  • 核心描述：当字符串存在 '*' 字符时，删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，可以删除任意一个。返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串
  • 题意明确：
    • ① 每次都是删除当前字符串中最左边的 * ，删除 * 号的顺序是固定的，从左到右依次删除 * 号。（如果删除顺序不固定，每次任意删除一个 * 号 ，这题就会变得十分复杂）
    • ② 删除 * 号之后，还要删除一个 * 号左边字典序最小的一个字符。存在多个字典序最小的字符时，删除任意一个

• 分析：

  • 求 “删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串”。当 *字符 左边字典序最小的字符都只有一个时，操作后得到的字符是唯一确定的。 存在多个字典序最小的字符时，选择删除哪个就是关键。由于要删除的是字典序最小的字符，为了让最终字符串字典序最小，就要保留靠前的字符，删除最靠后的那个字符。

• 解题思路：

  • 遍历字符串，每次遇到 '*'号 都删除前面“字典序最小且下标最大” 的那个字符。为了快速地获取当前字符串中“字典序最小且下标最大” 的字符，在遍历字符串的过程中使用优先队列（堆）来对元素进行维护（字典序小的优先级高，字典序相同时下标越大的元素优先级高），遇到 *字符 时直接删除优先级最高的元素即可。依次记录被删除字符的下标，在初始字符串中排除这些字符 和 '*' 字符即为所求。

java代码

class Solution {

    public String clearStars(String s) {

        // 优先队列定义queue：字典序小的优先级高，字典序相同时下标越大的元素优先级高
        PriorityQueue<CharNode> queue = new PriorityQueue<CharNode>(
                (CharNode a, CharNode b) -> (a.ch == b.ch ? b.index - a.index : a.ch - b.ch));

        // removeSet：记录被删除字符的下标
        Set<Integer> removeSet = new HashSet<Integer>();

        // 遇到字符的时候，将字符和下标入队。遇到*号的时候，将队顶元素出队
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if ('*' == ch) {
                CharNode removeChar = queue.poll();
                removeSet.add(removeChar.index);
                continue;
            }
            CharNode newChar = new CharNode(ch, i);
            queue.offer(newChar);
        }

        // 没有移除的字符元素拼接得到最终答案
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch != '*' && !removeSet.contains(i)) {
                res.append(ch);
            }
        }
        return res.toString();

    }
}

class CharNode {
    // 字符
    char ch;
    // 字符在字符串中的下标
    int index;

    public CharNode(char ch, int index) {
        this.ch = ch;
        this.index = index;
    }
}