Medium

题目描述

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

当存在 '*' 时，执行以下操作：

  • 删除最左边的 '*' 和它左边字典序最小的非 '*' 字符。如果有多个最小字符，你可以删除其中任意一个。

返回移除所有 '*' 字符后字典序最小的结果字符串。

示例 1：

输入：s = "aaba*"
输出："aab"
解释：我们应该删除一个 'a' 字符和 '*'。如果我们选择 s[3]，s 变成字典序最小的。

示例 2：

输入：s = "abc"
输出："abc"
解释：字符串中没有 '*'。

提示：

  • 1 <= s.length <= 10^5
  • s 只包含小写英文字母和 '*'
  • 输入保证可以删除所有 '*' 字符

解题思路

这道题的核心思想是贪心算法。我们需要处理每个星号时，删除它左边字典序最小的字符，以确保最终结果字典序最小。

解题思路：

  1. 栈 + 哈希表方法（推荐）：使用栈来维护当前字符，用哈希表记录每个字符的索引位置。遇到星号时，找到当前栈中字典序最小的字符进行删除。

  2. 标记数组方法：遍历字符串，用布尔数组标记要删除的字符。遇到星号时，向左查找最小字符并标记删除。

  3. 优先队列方法：使用最小堆存储字符及其位置，遇到星号时从堆顶取最小字符删除。

详细分析：

  • 关键在于理解"左边最小字符"的含义：不是位置最左的最小字符，而是值最小的字符
  • 需要高效地找到并删除指定字符，栈结构配合哈希表最为合适
  • 最终构造结果时，保持原有的相对顺序

核心思想是维护一个动态的字符集合，能够快速找到最小字符并删除。

代码实现

class Solution {
public:
    string clearStars(string s) {
        vector<char> stk;
        unordered_map<char, vector<int>> charIndices;
        
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '*') {
                // 找到栈中最小的字符
                char minChar = 'z' + 1;
                for (auto& p : charIndices) {
                    if (!p.second.empty() && p.first < minChar) {
                        minChar = p.first;
                    }
                }
                
                // 删除最小字符的最后一个出现位置
                if (minChar <= 'z') {
                    int idx = charIndices[minChar].back();
                    charIndices[minChar].pop_back();
                    if (charIndices[minChar].empty()) {
                        charIndices.erase(minChar);
                    }
                    stk[idx] = 0; // 标记为删除
                }
            } else {
                charIndices[s[i]].push_back(stk.size());
                stk.push_back(s[i]);
            }
        }
        
        string result;
        for (char c : stk) {
            if (c != 0) {
                result += c;
            }
        }
        return result;
    }
};

class Solution:
    def clearStars(self, s: str) -> str:
        stk = []
        char_indices = {}
        
        for i, c in enumerate(s):
            if c == '*':
                # 找到栈中最小的字符
                if char_indices:
                    min_char = min(char_indices.keys())
                    idx = char_indices[min_char].pop()
                    if not char_indices[min_char]:
                        del char_indices[min_char]
                    stk[idx] = None  # 标记为删除
            else:
                if c not in char_indices:
                    char_indices[c] = []
                char_indices[c].append(len(stk))
                stk.append(c)
        
        return ''.join(c for c in stk if c is not None)

public class Solution {
    public string ClearStars(string s) {
        List<char?> stk = new List<char?>();
        Dictionary<char, List<int>> charIndices = new Dictionary<char, List<int>>();
        
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '*') {
                // 找到栈中最小的字符
                if (charIndices.Count > 0) {
                    char minChar = charIndices.Keys.Min();
                    int idx = charIndices[minChar].Last();
                    charIndices[minChar].RemoveAt(charIndices[minChar].Count - 1);
                    if (charIndices[minChar].Count == 0) {
                        charIndices.Remove(minChar);
                    }
                    stk[idx] = null; // 标记为删除
                }
            } else {
                if (!charIndices.ContainsKey(s[i])) {
                    charIndices[s[i]] = new List<int>();
                }
                charIndices[s[i]].Add(stk.Count);
                stk.Add(s[i]);
            }
        }
        
        return string.Concat(stk.Where(c => c.HasValue).Select(c => c.Value));
    }
}

var clearStars = function(s) {
    const stk = [];
    const charIndices = new Map();
    
    for (let i = 0; i < s.length; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × 26) = O(n)n为字符串长度，每次查找最小字符最多遍历26个字母
空间复杂度O(n)栈和哈希表的存储空间