日期：2026年7月19日
LeetCode 題目連結：1081. Smallest Subsequence of Distinct Characters
解題想法
中等難度題。題目給一個字串 $s$，回傳字串中最小字典序的子字串，而且子字串之中每個字母只能出現一次。這題可以用單調隊列解題，隊列中的字母依照字典序排列，遇到新的字母 c 時，從隊列最後面移除字典序大於 c 的字母。在 Python 可以用 list 或是 string 儲存隊列，在 C++ 可以用 vector 或是 string 儲存隊列。另外要記錄每個字母最後一次於 s 出現的索引值，以及隊列中目前已選的字母。
Python 程式碼
用字典儲存索引值及已選的字母，用串列儲存隊列。Runtime: 3 ms, beats 38.55%. Memory: 19.24 MB, beats 75.23%.
class Solution:
def smallestSubsequence(self, s: str) -> str:
# 記錄 s 之中每個字母最後一次出現的索引值
lastIdx = {chr(i + ord('a')): -1 for i in range(26)}
for i, c in enumerate(s):
lastIdx[c] = i
# 單調隊列，t 之中的字母按照字典序排列，used 記錄 t 之中是否有字母 c
t = []
used = {chr(i + ord('a')): False for i in range(26)}
for i, c in enumerate(s):
if used[c]: continue # 已有字母 c，跳過
# 如果 t 有資料，c 小於 t 最後一項，而且 i 小於 t[-1] 最後一次出現的索引值
# 後面還有與 t[-1] 相同的字母可以加入，先移除
while t and c < t[-1] and i < lastIdx[t[-1]]:
used[t.pop()] = False # 移除 t[-1] 並重設 used
# c 加入 t 最後面
t.append(c)
used[c] = True
# 接成字串並回傳
return "".join(t)
用串列儲存索引值、已選的字母及隊列。Runtime: 3 ms, beats 38.55%. Memory: 19.55 MB, beats 75.23%.
class Solution:
def smallestSubsequence(self, s: str) -> str:
# 記錄 s 之中每個字母最後一次出現的索引值
lastIdx = [-1] * 26
for i, c in enumerate(s):
lastIdx[ord(c) - ord('a')] = i
# 單調隊列，t 之中的字母按照字典序排列，used 記錄 t 之中是否有字母 c
t = []
used = [False] * 26
for i, c in enumerate(s):
if used[ord(c) - ord('a')]: continue # 已有字母 c，跳過
# 如果 t 有資料，c 小於 t 最後一項，而且 i 小於 t[-1] 最後一次出現的索引值
# 後面還有與 t[-1] 相同的字母可以加入，先移除
while t and c < t[-1] and i < lastIdx[ord(t[-1]) - ord('a')]:
used[ord(t.pop()) - ord('a')] = False # 移除 t[-1] 並重設 used
# c 加入 t 最後面
t.append(c)
used[ord(c) - ord('a')] = True
# 接成字串並回傳
return "".join(t)
用串列儲存索引值、已選的字母，用字串儲存隊列。Runtime: 3 ms, beats 38.55%. Memory: 19.36 MB, beats 39.11%.
class Solution:
def smallestSubsequence(self, s: str) -> str:
# 記錄 s 之中每個字母最後一次出現的索引值
lastIdx = [-1] * 26
for i, c in enumerate(s):
lastIdx[ord(c) - ord('a')] = i
# 單調隊列，t 之中的字母按照字典序排列，used 記錄 t 之中是否有字母 c
t = ""
used = [False] * 26
for i, c in enumerate(s):
if used[ord(c) - ord('a')]: continue # 已有字母 c，跳過
# 如果 t 有資料，c 小於 t 最後一項，而且 i 小於 t[-1] 最後一次出現的索引值
# 後面還有與 t[-1] 相同的字母可以加入，先移除
while t and c < t[-1] and i < lastIdx[ord(t[-1]) - ord('a')]:
used[ord(t[-1]) - ord('a')] = False # 移除 t[-1] 並重設 used
t = t[:-1]
# c 加入 t 最後面
t += c
used[ord(c) - ord('a')] = True
# 回傳 t
return t
