📘 題目敘述
給定一個字串 s，請移除重複字母，讓每個字母都只出現一次。
同時還要保證最後得到的結果，在所有可能答案中，字典序最小。
條件限制
1 <= s.length <= 10^4s只包含小寫英文字母
🧠 解題思路
我這題的想法是用 greedy 搭配 monotonic stack。
因為題目不只是要把重複字母刪掉，還要求最後答案的字典序最小，所以我在掃字串時，會盡量讓前面的字元小一點。
如果目前要放進答案的字元 c 比 stack 頂端更小，而且 stack 頂端那個字元後面還會再出現，那我就可以先把頂端彈掉，等之後再放回來。
這樣可以讓比較小的字元更早出現在答案裡，字典序就會更小。
所以整體做法是：
- 用
count記錄每個字元後面還剩幾次 - 用
check記錄某個字元目前是不是已經在 stack 裡了 - 用
stack維護目前建出來的答案
每次處理新字元時：
- 先更新它剩餘次數
- 如果它已經在 stack 裡，就跳過
- 否則就檢查能不能把 stack 頂端較大的字元彈掉
- 最後再把目前字元放進 stack
所有變數
count：記錄每個字母目前還剩幾次還沒處理到check：記錄每個字母目前是否已經在 stack 裡st：monotonic stack，維護目前答案的字元順序ans：最後從 stack 還原出來的答案字串
🪜 主要流程步驟
1. 先統計每個字元總共出現幾次
我先用 count 把整個字串裡每個字母的出現次數都統計起來：
vector<int> count(26, 0);
for (char c : s) {
count[c - 'a']++;
}
這一步很重要，因為後面我在決定要不要把 stack 頂端字元彈掉時， 要知道那個字元未來還會不會再出現。
如果後面不會再出現，那就不能亂彈，不然答案就會少掉那個字母。
2. 用 check 記錄哪些字元已經在答案裡
我另外開一個 check 陣列：
vector<bool> check(26, false);
它的用途是記錄某個字母目前是不是已經放進 stack 裡了。
因為題目要求每個字母最後只能出現一次， 所以如果某個字元已經在 stack 裡，後面再遇到同樣字元時，就可以直接跳過，不需要重複放進去。
3. 逐個掃描字串，決定每個字元要不要放進 stack
接著我開始從左到右掃字串中的每個字元 c。
每次先做：
count[c - 'a']--;
這表示目前這個字元已經被我處理到了，所以它「後面還剩幾個」的數量要先扣掉一。
接著如果這個字元已經在 stack 裡，也就是：
if (check[c - 'a']) continue;
那我就直接跳過。 因為它已經存在答案中了，不需要再放一次。
4. 如果 stack 頂端比較大，而且之後還會再出現，就把它彈掉
這題最核心的地方就在這個 while：
while (!st.empty() && st.top() > c && count[st.top() - 'a'] > 0) {
check[st.top() - 'a'] = false;
st.pop();
}
這段意思是：
!st.empty()：stack 不能是空的st.top() > c：目前 stack 頂端字元比現在這個字元大count[st.top() - 'a'] > 0：而且那個頂端字元後面還會再出現
如果這三個條件都成立，我就可以放心把頂端字元先彈掉。
原因是：
- 目前有一個更小的字元
c可以提早放進答案 - 被彈掉的字元之後還找得到，不會真的消失
所以這樣做可以讓答案的字典序變得更小，而且又不會漏掉任何必須保留的字母。
另外在彈掉之前，我也要先把：
check[st.top() - 'a'] = false;
設回去，表示這個字元現在已經不在 stack 裡了，之後如果再遇到它，還可以重新放回來。
5. 把目前字元放進 stack，並標記已出現
當前面的彈出動作都做完之後，就代表目前這個字元 c 已經找到它現在最適合放的位置了。
所以我就把它 push 進 stack：
st.push(c);
check[c - 'a'] = true;
這代表：
- 目前答案尾端加入了這個字元
- 而且它已經存在於 stack 中，之後再遇到相同字元時就不能重複加入
6. 最後把 stack 還原成字串答案
當整個字串都掃完之後，stack 裡就放著最後答案的字元，只是順序是由底到頂。
所以我最後用一個字串 ans 把它倒回來
因為 stack 是後進先出，所以我每次把頂端字元接到 ans 前面，
這樣最後組出來的字串順序才會正確。
最後回傳 ans 就可以了。
⏱️ 複雜度
設 n = s.length。
- 時間複雜度：
O(n)每個字元最多只會被 push 進 stack 一次、pop 出來一次，所以整體還是線性時間。 - 空間複雜度：
O(n)stack 最多會放進n個字元；另外count和check是固定大小。
💻 程式碼實作
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> count(26, 0);
vector<bool> check(26, false);
for (char c : s) {
count[c - 'a']++;
}
stack<char> st;
for (char c : s) {
count[c - 'a']--;
if (check[c - 'a']) continue;
while (!st.empty() && st.top() > c && count[st.top() - 'a'] > 0) {
check[st.top() - 'a'] = false;
st.pop();
}
st.push(c);
check[c - 'a'] = true;
}
string ans = "";
while (!st.empty()) {
ans = st.top() + ans;
st.pop();
}
return ans;
}
};