【力扣第 400 场周赛】Leetcode 删除星号以后字典序最小的字符串

1. 删除星号以后字典序最小的字符串

题目链接

---

• 🍎 解题思路：
• 遇到 *就删除一个字符，为了满足题意，要删除字典序最小的字符，那么假如有多个字典序最小的字符我们该删除哪个呢？ — 我们应该删除离 * 最近、靠右边的那个字符。
• 为什么呢？ 因为：我们找到的就是字典序最小的字符，要满足整个字符串字典序最小，所以 应该将该字典序最小的字符多多的留在字符串的前面，删除后面的。

---

• 🍎 解题难点： 不知道怎么删除离 * 最近的字典序最小的字符
• 因为只有小写字母，所以用 26个栈将*前的字母的下标存储起来，因为栈是满足 后进先出的，所以刚好满足了我们要删除离 * 最近的字母条件（需要遍历一遍 26个栈噢）

---

class Solution {// 标记当前字符的下标是否被删除bool del[100010];public:string clearStars(string s) {// 将每个字母对应的下标都存入这个栈中 a --- 对应  0stack<int> st[26];for (int i = 0; i < s.size(); i++){char ch = s[i];if (ch != '*'){int num = ch - 'a';st[num].push(i);}else{del[i] = true;for (int j = 0; j < 26; j++){if (!st[j].empty()){int index = st[j].top();st[j].pop();del[index] = true;break;}}}}string res = "";for (int i = 0; i < s.size(); i++)if (!del[i])res += s[i];return res;}
};