前言
这是力扣的 2390 题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。
慢慢开始栈的模块了，这道题是一道非常好的栈的例题，很有代表性。
一、题目描述
给你一个包含若干星号 * 的字符串 s 。
在一步操作中，你可以：
- 选中
s中的一个星号。 - 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。
返回移除 所有 星号之后的字符串。
注意：
- 生成的输入保证总是可以执行题面中描述的操作。
- 可以证明结果字符串是唯一的。
示例 1：
代码语言：javascript复制输入：s = "leet**cod*e"
输出："lecoe"
解释：从左到右执行移除操作：
- 距离第 1 个星号最近的字符是 "leet**cod*e" 中的 't' ，s 变为 "lee*cod*e" 。
- 距离第 2 个星号最近的字符是 "lee*cod*e" 中的 'e' ，s 变为 "lecod*e" 。
- 距离第 3 个星号最近的字符是 "lecod*e" 中的 'd' ，s 变为 "lecoe" 。
不存在其他星号，返回 "lecoe" 。示例 2：
代码语言：javascript复制
输入：s = "erase*****"
输出：""
解释：整个字符串都会被移除，所以返回空字符串。提示：
1 <= s.length <= 105s由小写英文字母和星号*组成s可以执行上述操作
二、题解
2.1 用 stringBuilder 模拟栈
思路与算法：
这道题要求返回字符串 sss 移除所有星号之后的字符串。可以模拟生成字符串的过程得到移除所有星号之后的字符串。对于每个输入字符，执行如下操作。
- 如果输入字符不是星号，则将输入字符拼接到字符串的末尾。
- 如果输入字符是星号，则移除字符串的末尾字符。由于给定的字符串保证总是可以执行移除操作，因此不需要判断字符串是否为空。
由于每次遇到星号时移除字符串的末尾字符，符合后进先出的规则，因此可以使用栈模拟字符串的输入，栈底对应字符串的首端，栈顶对应字符串的末尾。
实现方面，可以使用可变字符串模拟栈，遍历结束之后，可变字符串的内容即为结果字符串。
2.2 传统栈实现
思路与算法：
读题可知，题目要求我们对串进行删除'*'元素操作。
注意题目对删除要求的说法：“移除星号左侧最近的那个非星号字符，并移除该星号自身。”
一说到左侧最近这几个字眼就要眼睛放光了，所谓删除左侧，也就说要删除上一次遍历操作的元素，也就是说这个操作是和时间顺序有联系的，回想起我们曾经学过数据结构，有哪种结构是对元素操作的先后顺序密切相关的呢？
相信你一定就能快速思索出来答案：队列 和 栈。
- 队列，先进先出，对最旧的那批元素先进行操作。
- 栈，后进先出，对最新的那批元素先进进行操作。
显然，要删除离'*'最近的元素肯定是用栈最好，因为要遍历到'*'号时，要删除的左侧元素就我们上次循环遍历过的。
三、代码
3.1 用 stringBuilder 模拟栈
Java版本：
代码语言：javascript复制class Solution {
public String removeStars(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i ) {
if(s.charAt(i)=='*'){
sb.deleteCharAt(sb.length()-1);
}else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}C 版本：
代码语言：javascript复制class Solution {
public:
string removeStars(string s) {
//创建一个答案串
string ans;
for(auto c : s){
if(c != '*'){
ans.push_back(c);
}else{
ans.pop_back();
}
}
return ans;
}
};3.2 传统栈实现
Java版本：
代码语言：javascript复制class Solution {
public String removeStars(String s) {
ArrayDeque<Character> deque = new ArrayDeque<>();
for (int i = 0; i < s.length(); i ) {
if (s.charAt(i) == '*') {
deque.pollLast();
} else {
deque.add(s.charAt(i));
}
}
StringBuilder sb = new StringBuilder();
for (Character c : deque) {
sb.append(c);
}
return sb.toString();
}
}C 版本：
代码语言：javascript复制class Solution {
public:
string removeStars(string s) {
std::stack<char> stack;
for (auto c : s) {
if (stack.empty()) {
stack.push(c);
continue;
}
if (c == '*') {
stack.pop();
} else {
stack.push(c);
}
}
string res;
while (!stack.empty()) {
res = stack.top();
stack.pop();
}
std::reverse(res.begin(), res.end());
return res;
}
};Python版本：
代码语言：javascript复制class Solution:
def removeStars(self, s: str) -> str:
st = []
for c in s:
if c == '*': st.pop()
else: st.append(c)
return ''.join(st)Go版本：
代码语言：javascript复制func removeStars(s string) string {
st := []rune{}
for _, c := range s {
if c == '*' {
st = st[:len(st)-1]
} else {
st = append(st, c)
}
}
return string(st)
}四、复杂度分析
4.1 用 stringBuilder 模拟栈
- 时间复杂度：O(n)，其中 n 为 s 的长度。
- 空间复杂度：O(n)。
4.2 传统栈实现
- 时间复杂度：O(n)，其中 n 为 s 的长度。
- 空间复杂度：O(n)。
