去除重复字母（不同字符的最小序列）问题
去除重复字母（不同字符的最小序列）问题
作者：Grey
原文地址：去除重复字母（不同字符的最小序列）问题
题目描述
LeetCode 316. Remove Duplicate Letters
LeetCode 1081. Smallest Subsequence of Distinct Characters
思路
由于题目说明了，字符串都是小写字母，所以第一步，
我们可以通过设置一个含有26个元素的数组来统计每个字符出现的频率
char[] str = s.toCharArray();
int[] map = new int[26];
for (char c : str) {
map[c - 'a']++;
}
通过如上方法，就可以得到每个字符的词频，
第二步，我们设置两个指针
int l = 0;
int r = 0;
先移动r指针，r每次移动一个位置，就把这个位置字符的词频减少一个，如果r某个时刻来到i位置，i位置的字符词频减少一个后就没有了，这就说明从[l...r]区间可以找到一个最小ASCII的字符开始结算了，假设[l...r]的最小ASCII字符在p位置，则我们需要做如下处理：
第一步： 将p位置的字符加入结果字符串中。
第二步：将p位置的词频设置为-1，便于标识p位置的字符已经使用过了，下次再遇到可以直接跳过：map[str[p]-'a']=-1
第三步：将[p+1...r]的字符词频重新加1，因为这部分的字符是减多了的。
第四步：r和l都来到p+1位置，继续上述处理流程。
示例图如下：
原始串和词频表如下：
接下来r位置字符的词频减少一个，r来到下一个位置
此时没有任何词频即将减少为0，继续移动r，
接下来移动r,注：此时d的词频即将减少到0，
接下来，就开始收集第一个元素，即在[l...r]区间内，找到ASCII最小的元素，即2号位置的a元素，此时，将a收集到结果字符串中，并且记录下a此时位置，即p=2。
然后，我们需要把整个字符串中a的词频设置为-1，表示a字符已经收集过了，即
map['a'-'a']=-1。
最后，由于a位置是收集到的位置，而r已经遍历到了3号位置的d元素，所以从a所在的位置到r位置中的所有元素，都要重新加一次词频（因为每次移动r会删除词频）。
完整代码如下：
public static String removeDuplicateLetters(String s) {
char[] str = s.toCharArray();
int[] map = new int[26];
for (char c : str) {
map[c - 'a']++;
}
StringBuilder sb = new StringBuilder();
int l = 0;
int r = 0;
while (r < str.length) {
if (map[str[r] - 'a'] == -1 || --map[str[r] - 'a'] > 0) {
// r在一个已经处理过的位置或者r上的词频减掉后没有到0，说明现在
// 还没有来到需要统计的时刻
// r放心++
r++;
} else {
// r位置的词频已经减少到0了
// 可以结算了
int p = l;
for (int i = l; i <= r; i++) {
if (map[str[i] - 'a'] != -1 && str[i] < str[p]) {
p = i;
}
}
if (map[str[p] - 'a'] != -1) {
// 结算的位置必须是有效位置
sb.append(str[p]);
// 结算完毕后，将这个位置的词频设置为-1，便于后续判断此位置是否已经被用过
map[str[p] - 'a'] = -1;
}
for (int i = p + 1; i <= r; i++) {
// [p+1,r]之间的位置的字符，把词频还原回来，因为这部分词频是减多了的
if (map[str[i] - 'a'] != -1) {
map[str[i] - 'a']++;
}
}
l = p + 1;
r = l;
}
}
return sb.toString();
}
