📝个人主页：五敷有你
🔥系列专栏：算法分析与设计
⛺️稳中求进，晒太阳
题目
示例
示例 1：
输入：s = "bcabc" 输出："abc"
示例 2：
输入：s = "cbacdcbc" 输出："acdb"
思路
贪心 + 单调栈实现
【字符串删除一个字符使其字典序最小的贪心策略】：
对于两个长度相同的字符串，最左边不同的字符决定了其字典序大小，例如，对于 A = xxaxxx，B = xxbxxx，如果 a > b， 则 A > B。
哪个字符串大取决于两个字符串中第1个对应不相等的字符，所以我们应该将最小的字符尽可能的放在前面。
对于一个字符串s[0...n-1]，如果必须删除1个字符使其删除后的字符串字典序最小
【删除策略】就是：
1）从左往右找到第1个降序的位置i（s[i]>s[i+1]），删除s[i]；
例："abcb",应该删除'c'字符，这样删除一个字符后，字典序最小
2）如果不存在降序位置，即字符串是升序的（[i+1]>=[i]），删除末尾字符（字典序最大）；
例："abcd"，应该删除'd'字符，这样删除一个字符后，字典序最小如果删除k个字符使其删除后字典序最小，等同与先删除1个字符使其字典序最小，删除后的新字符串便形成了一个【子问题】，继续同样策略。
算法思路
维护一个词频表，表示每个字符后续可供选择的数量
从左往右遍历每个字符，每次遍历，当前字符消耗1个（后续可供选择的数量减1）
1. 如果当前字符后续已经没有可供选择数量了（<1），当前字符没得选了，只能选择要；
2. 如果当前字符后续仍有数量（>=1），可以选择要当前字符，也可以选择不要，怎么选？【一个字符要还是不要的选择策略】是：
借助于上面描述的【字符串删除一个字符使其字典序最小的贪心策略】：
如果当前保留的字符串的前一个字符字典序 > 当前字符，删除前一个字符，选择要当前字符；
否则，选择删除当前字符，要前一个字符【通过单调栈维护当前已经选择的字符】：
如果选择要一个字符，是否可以入栈，还需要判断之前是否已经选择过该字符：该字符是否存在单调栈中。
由于只有26个小写字母，可用一个bool数组即可代替Set结构。
代码实现
public static String removeDuplicateLetters(String s) {
if (s.length() == 1) return s;
int[] charCounts = new int[26]; // 剩余词频表（题目规定只有小写字母）：该字符剩余可供选择的数量
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
charCounts[c-'a']++;
}
// 双端队列维护单调栈，栈底（小）-> 栈顶（大）小于等于
LinkedList<Character> deque = new LinkedList<>();
boolean[] isCharInStack = new boolean[26]; // Set，表示对应字符是否已经在单调栈中（该字符是否已被选择保留）
for (int i = 0; i < s.length(); i++) {
char cur = s.charAt(i);
charCounts[cur - 'a']--;
// cur已在栈中，丢弃当前字符
if (isCharInStack[cur - 'a']) continue;
// 如果栈顶字符字典序大于当前字符，选择要当前字符，并考虑删除栈顶字符（如果栈顶字符在后面还有数量可选，删除栈顶字符）
while (!deque.isEmpty() && deque.peek() > cur && charCounts[deque.peek()-'a'] >= 1) {
// 删除栈顶字符
Character popChar = deque.pop();
isCharInStack[popChar - 'a'] = false; // 栈中已不存在该字符
}
// 选择要该字符，入栈
deque.push(cur);
isCharInStack[cur - 'a'] = true;
}
StringBuilder sb = new StringBuilder();
// 双端队列从栈底，逆序输出
while (!deque.isEmpty()) {
sb.append(deque.pollLast());
}
return sb.toString();
}