[LeetCode] 每日一题 3170. 删除星号以后字典序最小的字符串（优先队列 + 贪心算法）

题目描述

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

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

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

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

题目链接

https://leetcode.cn/problems/lexicographically-minimum-string-after-removing-stars

示例输入

示例 1

输入：s = "aaba*"

输出："aab"

解释：

删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。

示例 2

输入：s = "abc"

输出："abc"

解释：

字符串中没有 '*' 字符。

提示

• 1 <= s.length <= 10^5

• s 只含有小写英文字母和 '*' 字符

• 输入保证操作可以删除所有的 '*' 字符

解题思路

这道题刚看上去可能会让人联想到栈的思路，但仔细分析之后其实更适合用 贪心算法 来解决。我们想要构造的，是一个在删除所有 * 之后的 字典序最小字符串，而且每次只能删掉最左边的 * 以及它左侧的某一个字符。

那我们就得想清楚两件事：

1. 谁来删除？——当然是 *

2. 删谁？——删掉这个 * 左边字典序最小的字符。如果有多个一样的，那就删右边那个

因此我们需要一个结构来动态维护当前所有未被删除字符中，最小字典序且尽量靠右的字符。这时就想到用 优先队列（堆） 来模拟。

这里的关键是：往堆里放的是字符的下标，而不是字符本身。排序规则是：

• 字典序小的字符优先

• 如果字典序相同，下标大的优先（因为要尽量删除靠右的）

每遇到一个 *，就从堆顶弹出那个被它“删除”的字符的下标，并标记它和这个星号都删掉。最后我们再拼出剩下的字符即可

代码实现

class Solution {
    public String clearStars(String s) {
        char[] charArray = s.toCharArray();
        int n = charArray.length;
        PriorityQueue<Integer> queue = new PriorityQueue<>((e1, e2) -> {
            if (charArray[e1] == charArray[e2]) {
                return e2 - e1;
            }
            return charArray[e1] - charArray[e2];
        });
        for (int i = 0; i < n; i++) {
            if (charArray[i] == '*') {
                Integer index = queue.poll();
                charArray[index] = '*';
            } else {
                queue.add(i);
            }
        }
        StringBuilder ans = new StringBuilder();
        for (char c : charArray) {
            if (c != '*') {
                ans.append(c);
            }
        }
        return ans.toString();
    }
}

复杂度分析

• 时间复杂度：

  • O(n log n)，其中 n 是字符串的长度。每个字符最多被插入和删除一次优先队列，每次操作复杂度为 log n

• 空间复杂度：

  • O(n)，主要用于存储字符索引的优先队列和字符数组

总结

这道题的关键在于抓住“删除最左 * 及其左侧最小字符”这个操作规则。与常见的“遇到 * 就弹栈”的做法不同，这里需要我们精确选择要删的字符——字典序最小、位置最靠右。因此，堆 + 贪心策略 成为更优解法。

整个题的实现过程中，我也体会到堆排序的灵活用法，特别是在需要做多维优先级比较的时候，记得索引常常能帮我们完成更多的逻辑控制🫠🫠

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。