1.題目
給你一個包含若干星號 * 的字符串 s 牌捷。
在一步操作中粗恢，你可以：
選中 s 中的一個星號。
移除星號 左側 最近的那個 非星號 字符缴守，并移除該星號自身。
返回移除 所有 星號之后的字符串镇辉。
注意：
生成的輸入保證總是可以執(zhí)行題面中描述的操作屡穗。
可以證明結果字符串是唯一的。
示例 1：
輸入：s = "leet*code"
輸出："lecoe"
解釋：從左到右執(zhí)行移除操作：
- 距離第 1 個星號最近的字符是 "leetcode" 中的 't' 忽肛，s 變?yōu)?"leecod*e" 村砂。
- 距離第 2 個星號最近的字符是 "leecode" 中的 'e' ，s 變?yōu)?"lecod*e" 屹逛。
- 距離第 3 個星號最近的字符是 "lecod*e" 中的 'd' 础废，s 變?yōu)?"lecoe" 。
不存在其他星號罕模，返回 "lecoe" 评腺。
示例 2：
輸入：s = "erase*****"
輸出：""
解釋：整個字符串都會被移除，所以返回空字符串淑掌。
提示：
1 <= s.length <= 105
s 由小寫英文字母和星號 * 組成
s 可以執(zhí)行上述操作
2.思路
-
方法：棧：先進后出
- 基本思想：
1.首先定義了一個 Stack 類蒿讥，并使用泛型來指定棧中元素的類型。然后抛腕，我們使用一個私有變量 elements 來保存棧中的元素芋绸。接著，我們定義了 push担敌、pop摔敛、top 和 isEmpty 四個方法來實現(xiàn)棧的基本功能。
2.push 方法用于向棧中添加元素柄错，我們可以使用 List 的 :: 操作符將新元素添加到 List 的頭部舷夺。
3.pop 方法用于彈出棧頂元素苦酱，我們使用模式匹配來處理空棧和非空棧的情況售貌。如果棧為空给猾，則返回 None，否則彈出 List 的頭部元素颂跨，并將剩余元素賦值給 elements敢伸。
4.top 方法用于獲取棧頂元素，如果 為空恒削，則返回 None池颈。
- 基本思想：
isEmpty 方法用于判斷棧是否為空，我們使用 List 的 isEmpty 方法來判斷钓丰。
3.代碼
object Solution {
def removeStars(s: String): String = {
import scala.collection.mutable._
val charArray: Array[Char] = s.toCharArray
val stringBuilder = new StringBuilder
val stack = new Stack[Char]
for(ch<-charArray){
if(ch=='*') stack.pop()
else stack.push(ch)
}
// 棧是先進后出躯砰，所以倒序進行拼接
for(i<- stack.length-1 to 0 by -1){
stringBuilder.append(stack(i))
}
return stringBuilder.toString()
}
}
4.復雜度分析
時間復雜度：O(N)
空間復雜度：O(N)
