拓展：数组去重问题（困难版）
原创约 2576 字
本文讲解的例题
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 1081. Smallest Subsequence of Distinct Characters | 1081. 不同字符的最小子序列 | 🟠 |
| 316. Remove Duplicate Letters | 316. 去除重复字母 | 🟠 |
关于去重算法，应该没什么难度，往哈希集合里面塞不就行了么？
最多给你加点限制，问你怎么给有序数组原地去重，这个我们前文 双指针技巧秒杀七道数组题目 讲过。
本文讲的问题应该是去重相关算法中难度最大的了，把这个问题搞懂，就再也不用怕数组去重问题了。
这是力扣第 316 题「去除重复字母」，题目如下：
316. 去除重复字母 | 力扣 | LeetCode |
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"输出："abc"
示例 2：
输入：s = "cbacdcbc"输出："acdb"
提示：
1 <= s.length <= 104s由小写英文字母组成
注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
这道题和第 1081 题「不同字符的最小子序列」的解法是完全相同的，你可以把这道题的解法代码直接粘过去把 1081 题也干掉。
题目的要求总结出来有三点：
要求一、要去重。
要求二、去重字符串中的字符顺序不能打乱 s 中字符出现的相对顺序。
要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。
上述三条要求中，要求三可能有点难理解，举个例子。
比如说输入字符串 s = "babc"，去重且符合相对位置的字符串有两个，分别是 "bac" 和 "abc"，但是我们的算法得返回 "abc"，因为它的字典序更小。
按理说，如果我们想要有序的结果，那就得对原字符串排序对吧，但是排序后就不能保证符合 s 中字符出现顺序了，这似乎是矛盾的。
其实这里会借鉴前文 单调栈解题框架 中讲到的「单调栈」的思路，没看过也无妨，等会你就明白了。
我们先暂时忽略要求三，用「栈」来实现一下要求一和要求二，至于为什么用栈来实现，后面你就知道了：