题目大意：
不同字符的最小子序列
返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
示例 1：
输入：”cdadabcc”
输出：”adbc”
示例 2：
输入：”abcd”
输出：”abcd”
示例 3：
输入：”ecbacba”
输出：”eacb”
示例 4：
输入：”leetcode”
输出：”letcod”
提示：
1 <= text.length <= 1000
text 由小写英文字母组成
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1081
解题思路分析：
题目要求返回的子序列必须是要包含所有出现过的字符1次。因此子序列的长度一定是原字符串中包含的字符种类的个数。同时这个子序列必须满足字典顺序最小。要满足字典顺序最小这个条件，我们应该尽量让小的字母排到前面，大的字母排在后面。不过我们还要考虑到一种情况，如果当前字符在字符串中仅出现过一次，或者该字符在当前位置是最后一次出现并且我们还未将其添加到结果中，那么我们需要无条件将其加入到结果中，否则我们会错过该字符。
本题可以使用Stack栈来解决，原则上组成一个递增栈是我们理想的目标。
我们从第一位开始循环字符串，如果当前字符大于Stack中的最后一位，我们直接将其插入到栈中，反之，如果当前字符小于Stack中的最后一位，我们就该考虑是否要将栈中的最后一位踢出栈，是否该踢出的条件取决于这个最后一位的字符在字符串当前位置之后是否还存在，如果存在，则可以踢出，因为之后还有机会再将其加进来。如果没有，则不能踢出，原因是踢出之后我们再没有机会添加这个字符了，这时即使当前字符小于它，也不得不将当前字符添加到它的后面。另外一种情况，如果当前字符已经存在于Stack之中，由于每种字符只能出现一次，所以我们无需理会，直接跳过即可。
编程思路大概如下：
- 先循环一遍字符串，将每种字符出现的次数计算出来。
- 定义一个Stack，建立一个递增栈。（不能递增的部分除外）
- 将栈中的字符打印成字符串返回。
完整代码：
public String smallestSubsequence(String text) {
int[] count = new int[26]; // 定义一个用于计算字符出现次数的数组
for(int i=0;i<text.length();i++){ // 循环字符串
count[text.charAt(i)-'a']++; // 更新每种字符出现的次数
}
Stack<Character> stack = new Stack<>(); // 定义一个栈
for(int i=0;i<text.length();i++){ // 循环字符串
char c = text.charAt(i); // 取得当前字符
count[c-'a']--; // 更新当前字符剩余个数
if(stack.contains(c)){ // 如果当前字符已经存在于Stack中，直接跳过
continue;
}
if(!stack.isEmpty()){ // 当Stack不为空
char p = stack.peek(); // 取得Stack中最后一个元素
// 如果当前字符小于这个元素，并且这个元素还有剩余
while(c < p && count[p-'a']>0){
stack.pop(); // 将最后一个元素踢出栈
if(stack.isEmpty()){ // 当Stack为空，结束循环
break;
}
p = stack.peek(); // 重新取得Stack中最后一个元素，继续循环比较
}
}
stack.push(c); // 将当前字符加入栈
}
String res=""; // 定义返回结果
while(!stack.isEmpty()){ // 利用Stack，构建返回值
res = stack.pop() + res;
}
return res;
} 本解法用时3ms。
Runtime: 3 ms, faster than 51.81% of Java online submissions for Smallest Subsequence of Distinct Characters.
Memory Usage: 34.5 MB, less than 100.00% of Java online submissions for Smallest Subsequence of Distinct Characters.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/1081-smallest-subsequence-of-distinct-characters-解题思路分析/