Given a string
s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.Example 1:
Example 2:
Constraints:
1 <= s.length <= 104
sconsists of lowercase English letters.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
- 考虑a的情况，如果字符串有多个a那么为了输出最小的字符串那么肯定选择出现位置最早的a，这样他后面有更多的字符可以排序出更小的情况。之后考虑b，优选策略也是选择出现位置最早的情况，但是如果存在a字符在前面那么在a之后最近的b则是最优解。
- 从a-z遍历，保存确定好位置的字符位置
- 使用stack，首先记录每个字符最后出现的位置，循环字符串将其加入stack。如果当前的字符比stack尾的字符小并且stack尾最后出现的位置比当前位置大时，说明可以使用后面出现的相同字符。所以把stack尾字符出栈，持续这个流程知道当前字符找到合适的位置。