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

1. 题目描述

返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。

示例 1：

输入："cdadabcc"
输出："adbc"

示例 2：

输入："abcd"
输出："abcd"
示例 3：

输入："ecbacba"
输出："eacb"
示例 4：

输入："leetcode"
输出："letcod"

2. 解题思路

这道题的关键是“局部最优”，即当前字符要比栈里字符更大，即要永远保持前面字符的字典序越小越好，但要注意题目要求：必须包含所有的字符这一条件，可以用栈来解决，但因为栈有些操作并不好弄（缺少一些函数），所以可以用vector直接代替也行（效率反而更高了）。

2.1 C++

 1 class Solution {
 2 public:
 3     string smallestSubsequence(string s) {
 4         // 获取字符串长度
 5         int n = s.size();
 6         // 定义容器
 7         vector<char> obj;
 8         string ss = "";
 9         // 遍历所有字符
10         for(int i = 0; i < n; i++){
11             // 获取当前字符
12             char occ = s[i];
13             // 首先判断容器中是否已有当前字符，若有跳出当前循环
14             if(find(obj.begin(), obj.end(), occ) != obj.end()){
15                 continue;
16             }
17             // 判断是否出栈
18             // 1.容器部位空(!obj.empty())
19             // 2.当前元素小于栈顶元素(occ < obj.back())
20             // 3.在剩下的字符数组中查找当前元素位置i开始是否还会出现，
21             //   保证所有元素出现一次（s.find(obj.back(), i) != -1）
22             while(!obj.empty() && occ < obj.back() && s.find(obj.back(), i) != -1){
23                 // 出栈
24                 obj.pop_back();
25             }
26             // 入栈
27             obj.push_back(s[i]);
28         }
29         // 存储排序最小的子序列
30         for(auto o : obj){
31             ss += o;
32         }
33         return ss;
34     }
35 };

2.2 Java

 1 class Solution {
 2     public String smallestSubsequence(String s) {
 3         // 获取字符串长度
 4         int n = s.length();
 5         Stack<Character> obj = new Stack<>();
 6         StringBuilder ss = new StringBuilder();
 7         for(int i = 0; i < n; i++){
 8             char occ = s.charAt(i);
 9             if(obj.contains(occ)){
10                 continue;
11             }
12             while(!obj.empty() && occ < obj.peek() && s.indexOf(obj.peek(), i) != -1){
13                 obj.pop();
14             }
15             obj.push(occ);
16         }
17         for(Character o : obj){
18            ss.append(o);
19         }
20         return ss.toString();
21     }
22 }

2.3 Python

1. 贪心，遍历text，当前遍历到的字母c在字典序小于栈顶元素且后续还能找到当前栈顶元素时，就让栈顶弹出，然后把当前元素压进栈。

给栈一个初始元素可以减少循环过程中对栈存在的判断，相对于其他解答，需要说的一点是python的字符是可以直接比较大小的，不需要用ord()转成ascii码。

 1 class Solution:
 2     def smallestSubsequence(self, s: str) -> str:
 3         # 单栈实现
 4         ans = [' ']
 5         for i, c in enumerate(s):
 6             if c not in ans:
 7                 while c < ans[-1] and ans[-1] in s[i:]:
 8                     ans.pop()
 9                 ans += [c]
10         return ''.join(ans[1:])

2. 栈加哈希在in语句会明显快很多，python列表的in判断是

 1 class Solution:
 2     def smallestSubsequence(self, s: str) -> str:
 3         # 栈 + hash
 4         ans, d = [' '], set()
 5         for i, c in enumerate(s):
 6             if c not in d:
 7                 while ans[-1] > c and ans[-1] in s[i: ]:
 8                     d.remove(ans.pop())
 9                 ans += [c]
10                 d |= {c}
11         return ''.join(ans[1: ])
12

3. 结语

　　努力去爱周围的每一个人，付出，不一定有收获，但是不付出就一定没有收获！给街头卖艺的人零钱，不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)！

　如果客官喜欢小生的园子，记得关注小生哟，小生会持续更新(#^.^#)(#^.^#)。