目标
给你一个字符串 s 。它可能包含任意数量的 '' 字符。你的任务是删除所有的 '' 字符。
当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：
- 删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。
请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。
示例 1：
输入：s = "aaba*"
输出："aab"
解释：
删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。示例 2：
输入：s = "abc"
输出："abc"
解释：
字符串中没有 '*' 字符。说明：
- 1 <= s.length <= 10^5
- s 只含有小写英文字母和 '*' 字符。
- 输入保证操作可以删除所有的 '*' 字符。
思路
有一个包含任意数量 * 的字符串，每次操作可以删掉 * 以及它左侧的一个字典序最小的字符，如果有多个可以，删除任意一个。求删除所有 * 之后能够得到的 字典序最小的字符串。
贪心算法，优先删除左侧字典序最小且下标最大的字符即可。
代码
/**
* @date 2025-06-07 9:37
*/
public class ClearStars3170 {
public String clearStars(String s) {
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> {
int compare = a[0] - b[0];
if (compare != 0) {
return compare;
}
return b[1] - a[1];
});
char[] chars = s.toCharArray();
int n = chars.length;
for (int i = 0; i < n; i++) {
char c = chars[i];
if (c != '*') {
q.offer(new int[]{c, i});
} else {
q.poll();
}
}
char[] res = new char[q.size()];
PriorityQueue<int[]> tmp = new PriorityQueue<>((a, b) -> a[1] - b[1]);
tmp.addAll(q);
int i = 0;
while (!tmp.isEmpty()) {
int[] c = tmp.poll();
res[i++] = (char) c[0];
}
return new String(res);
}
}
性能
