移除字串中重複的字母，使每個字母只出現一次，並讓結果在所有可能解中字典序最小。
Example:
Input: s = “bcabc” Output: “abc”
Input: s = “cbacdcbc” Output: “acdb”
Intuition
TIP
核心思路：單調堆疊 + 貪心。維護一個遞增的結果堆疊；遇到較小的字母時，若堆疊頂端字母後面還會再出現，就把它彈掉以換取更小的字典序。
- 先記每個字母的「最後出現位置」
lastIndex - 掃描時，若當前字母已在堆疊中則跳過（每字母只留一個）
- 否則，當棧頂 > 當前字母 且 棧頂之後還會出現，彈出棧頂（之後再補）
- 用
inStack布林陣列 O(1) 判斷是否已在堆疊中
Approaches
⭐ Monotonic Stack + Greedy — O(n) / O(1)
- Idea: 維持結果遞增；可被「之後還會出現」的較大棧頂讓位給更小字母
- Time:
O(n)- 每個字母最多進出堆疊一次 - Space:
O(1)- 堆疊與輔助陣列至多 26 個字母
class Solution {
fun removeDuplicateLetters(s: String): String {
val lastIndex = IntArray(26)
for (i in s.indices) lastIndex[s[i] - 'a'] = i
val inStack = BooleanArray(26)
val stack = ArrayDeque<Char>()
for (i in s.indices) {
val c = s[i]
if (inStack[c - 'a']) continue // 已選過此字母
// 棧頂較大、且之後還會再出現 → 彈掉換更小字典序
while (stack.isNotEmpty() && stack.last() > c && lastIndex[stack.last() - 'a'] > i) {
inStack[stack.removeLast() - 'a'] = false
}
stack.addLast(c)
inStack[c - 'a'] = true
}
return stack.joinToString("")
}
}Note: Relation to 402 Remove K Digits
兩題都是「單調堆疊 + 貪心求字典序最優」：402 是移除 k 位數字使數字最小（不要求去重），本題是去重後使字典序最小。差別在彈出條件——本題多了「該字母之後是否還會出現」（不能把唯一一次出現的字母彈掉），402 則是限制彈出次數 k。
🔑 Takeaways
- Pattern: 單調堆疊配貪心，靠「之後是否還會出現」決定能否彈出讓位
- Key trick:
lastIndex判斷棧頂是否還有機會補回、inStack確保每字母只取一次。和 402 Remove K Digits、1209 Remove Adjacent Duplicates II 是同一套「堆疊維持最優前綴」的家族