Create 1081. 不同字符的最小子序列.md

itcharge · itcharge · commit 2621e522528c · 2022-01-10T15:47:21.000+08:00
diff --git a/Solutions/1081. 不同字符的最小子序列.md b/Solutions/1081. 不同字符的最小子序列.md
@@ -0,0 +1,55 @@
+## [1081. 不同字符的最小子序列](https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/)
+
+- 标签：栈、贪心、字符串、单调栈
+- 难度：中等
+
+## 题目大意
+
+给定一个字符串 `s`。
+
+要求：返回 `s` 字典序最小的子序列，该子序列包含 `s` 的所有不同字符，且只包含一次。
+
+## 解题思路
+
+针对题目的两个要求：包含所有不同字符，且只包含一次（去重）、子序列（不能打乱其他字符顺序）、字典序最小。我们来一一进行分析。
+
+1. 包含所有不同字符，且只包含一次（去重）：可以通过 **「使用哈希表存储字母出现次数」** 的方式，将每个字母出现的次数统计起来，再遍历一遍，去除重复的字母。
+2. 子序列（不能打乱其他字符顺序）：按顺序遍历，将非重复的字母存储到答案数组或者栈中，最后再拼接起来，就能保证不打乱其他字符顺序。
+3. 字典序最小：意味着字典序小的字母应该尽可能放在前面。
+   - 对于第 `i` 个字符 `s[i]` 而言，如果第 `0` ~ `i - 1` 之间的某个字符 `s[j]` 在 `s[i]` 之后不再出现了，那么 `s[j]` 必须放到 `s[i]` 之前。
+   - 而如果 `s[j]` 在之后还会出现，并且 `s[j]` 的字典序大于 `s[i]`，我们则可以先舍弃 `s[j]`，把 `s[i]` 尽可能的放到前面。后边再考虑使用 `s[j]` 所对应的字符。
+
+要满足第 3 条需求，我们可以使用 **「单调栈」** 来解决。我们使用单调栈存储 `s[i]` 之前出现的非重复、并且字典序最小的字符序列。整个算法步骤如下：
+
+- 先遍历一遍字符串，用哈希表 `letter_counts` 统计出每个字母出现的次数。
+- 然后使用单调递减栈保存当前字符之前出现的非重复、并且字典序最小的字符序列。
+
+- 当遍历到 `s[i]` 时，如果 `s[i]` 没有在栈中出现过：
+  - 则比较 `s[i]` 和栈顶元素 `stack[-1]` 的字典序。如果 `s[i]` 的字典序小于栈顶元素 `stack[-1]`，并且栈顶元素之后的出现次数大于 `0`，则将栈顶元素弹出。
+  - 然后继续判断 `s[i]` 和栈顶元素 `stack[-1]`，并且知道栈顶元素出现次数为 `0` 时停止弹出。此时将 `s[i]` 添加到单调栈中。
+- 从哈希表 `letter_counts` 中减去 `s[i]` 出现的次数，继续遍历。
+- 最后将单调栈中的字符依次拼接为答案字符串，并返回。
+
+## 代码
+
+```Python
+class Solution:
+    def smallestSubsequence(self, s: str) -> str:
+        stack = []
+        letter_counts = dict()
+        for ch in s:
+            if ch in letter_counts:
+                letter_counts[ch] += 1
+            else:
+                letter_counts[ch] = 1
+
+        for ch in s:
+            if ch not in stack:
+                while stack and ch < stack[-1] and stack[-1] in letter_counts and letter_counts[stack[-1]] > 0:
+                    stack.pop()
+                stack.append(ch)
+            letter_counts[ch] -= 1
+
+        return ''.join(stack)
+```
+
