题目描述：
给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例：
输入: "cbacdcbc"
输出: "acdb"
首先解释一下字典序。字典序是指从前到后比较两个字符串大小的方法。
首先比较第 1 个字符，如果不同则第 1 个字符较小的字符串更小；
如果相同则继续比较第 2 个字符 …… 如此继续，比较整个字符串的大小。
观察示例 1：bcabc。
字符 a 在字符串中只出现一次，根据题目要求，字符 a 必须被选取；
字符 b 出现了两次，显然选择 a后面的那个，因为字典序 ab 在 ba 前面。同理，有两个相同的字符 c ，我们选择后一个。因此，输出就是 abc。
再观察示例 2：cbacdcbc。
有 4 个字符：a、b、c、d。其中 a 和 d 只出现一次，必须被选取；
b 出现 2 次，一个在 a 前面，一个在 a 后面，显然保留在 a 后面的；
c 出现 4 次，我们把几种可能都列出来观察一下：
情况 1：cadb
情况 2：acdb（字典序最小）
情况 3：adcb
情况 4：adbc
一种最理想的情况是：abcd，在遍历的时候，遇到的字符串的 ASCII 值逐渐增大。
下面我们就思考，当遍历到的字符的 ASCII 值减少的时候，应该如何处理。
还看示例 1：已经读到了 bc，已经是字典序最小的排列。
即将读到的 a 比 c 的 ASCII 值小。如果 a 能排在 c 之前，就能得到一个比 ca 更小的字典序 ac。
那么 a 能不能排在 c 之前，就看 a 的后面还会不会出现字符 c，显然会。同理，由于字符 b 在将来还会出现，构成的字典序更小，因此舍弃之前的字符 b。
到此为止，应该想到我们需要借助栈帮助我们完成这题。
然后根据这个思路，我们再看一下示例 2：cbacdcbc。
栈.png
第 1 步：读到 c，入栈，此时栈中元素 [c]；
第 2 步：读到 b，b 比之前 a 小，c 在以后还会出现，因此 c 出栈，b 入栈，此时栈中元素 [b]；
第 3 步：读到 a，a 比之前 b 小，b 在以后还会出现，因此 b 出栈，a 入栈，此时栈中元素 [a]；
第 4 步：读到 c，c 比之前 a 大，直接让 c 入栈，此时栈中元素 [a, c]；
第 5 步：读到 d，d 比之前 d 大，直接让 d 入栈，此时栈中元素 [a, c, d]；
第 6 步：读到 c，这里要注意：此时栈中已经有 c 了，此时栈中元素构成的字符顺序就是最小的字典序，不可能舍弃之前的 c，而用现在的读到的 c，因此这个 c 不需要，直接跳过；
第 7 步：读到 b，b 比之前的 c 小，但是，后面不会再出现 b 了，因此 b 就应该放在这个位置，因此让 b 入栈，此时栈中元素 [a, c, d, b]；
第 8 步：读到 c，同第 6 步，这个 c 我们不需要。
于是，我们可以设计如下算法：
1、遍历字符串里的字符，如果读到的字符的 ASCII 值是升序，依次存到一个栈中；
2、如果读到的字符在栈中已经存在，这个字符我们不需要；
3、如果读到的 ASCII 值比栈顶元素严格小，看看栈顶元素在后面是否还会出现，如果还会出现，则舍弃栈顶元素，而选择后出现的那个字符，这样得到的字典序更小。
因为需要判断读到的字符在栈中是否已经存在，因此可以使用哈希表，又因为题目中说，字符只会出现小写字母，用一个布尔数组也是可以的，注意在出栈入栈的时候，需要同步更新一下这个布尔数组。
又因为要判断栈顶元素在后面是否会被遍历到，因此我们需要先遍历一次字符，存一下这个字符最后出现的位置，就能判断栈顶元素在后面是否会被遍历到。
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/remove-duplicate-letters/solution/zhan-by-liweiwei1419/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
Java代码：
class Solution {
public String removeDuplicateLetters(String s) {
int len = s.length();
if (len < 2) return s;
// 记录是否在已经得到的字符串中
boolean[] set = new boolean[26];
// 记录每个字符出现的最后一个位置
int[] lastAppearIndex = new int[26];
for(int i = 0;i < len;i++) {
lastAppearIndex[s.charAt(i) - 'a'] = i;
}
Deque<Character> stack = new ArrayDeque<>();
// 此时 `a` 作为哨兵，这个 `a` 永远不会被弹出
// 如此一来，在遍历的时候，就不用判断栈是否为空了
stack.push('a');
for(int i = 0;i < len;i++) {
char curChar = s.charAt(i);
if(set[curChar - 'a']) continue;
while(stack.peek() > curChar && lastAppearIndex[stack.peek() - 'a'] >= i) {
char top = stack.pop();
set[top - 'a'] = false;
}
stack.push(curChar);
set[curChar - 'a'] = true;
}
int size = stack.size();
StringBuilder result = new StringBuilder();
for(int i = 0;i < size - 1;i++) {
result.insert(0, stack.pop()); //这里用append会出错，暂时懒得查append和insert的区别了
}
return result.toString();
}
}
网友评论