[316] 去除重复字母

给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1:

输入："bcabc"

输出："abc"

示例 2:

输入："cbacdcbc"

输出："acdb"

注意：该题与 [1081] 不同字符的最小子序列 相同

这题算是集所有技巧于大成的去重题了，里面用到了许多的技巧。

首先审题，题目要求有三：

1. 对字符串去重
2. 不能打乱原有字符串的相对位置
3. 保证返回的字典序最小

先一步一步来看，条件二要求我们不能对原有字符串数组进行排序，这样我们最常用的数组去重方式（排序后使用快慢指针去重）就不能被使用了。

因此我们只能使用 hashMap 的方式来记录下出现过的元素，从而比对进行去重。

那么怎样保证条件三：最终的字典序最小呢？这个就是题目的难点了。

在插入一个字符的时候我们必须保证该字符之前的字符在字典序上要比当前字符小，不满足要求的需要被剔除，因此我们可以使用单调栈的方式来实现这个目的。当遇到栈顶元素字典序大于当前元素，则不断执行出栈操作，直到符合字典序为止。

那么这样做又引入了一个新的问题，当一个元素之后都不会再出现了，却因为在比较中字典序较大而被出栈了，那么我们就会永远的丢失这个元素，从而让结果有误。

因此我们还需要一个 countMap，在当前栈顶元素出栈之前判断之后是否还会有该元素，若没有则不能出栈该元素。（这里用循环去判断后面还有没有该元素在时间复杂度上就差了，用空间换下时间）。

之后我们只需要将栈中元素转换为字符串即可完成题目要求。

function removeDuplicateLetters(s: string): string {
  // 遍历字符串，统计每个字母的出现次数
  const countMap: Record<string, number> = {};
  for (const ch of s) {
    countMap[ch] = countMap[ch] ? countMap[ch] + 1 : 1;
  }
  const stack: string[] = [];
  const stackMap: Record<string, boolean> = {};
  for (const ch of s) {
    // 每遍历过一个字符，当前字符的 count 数 -1
    countMap[ch] -= 1;

    // 栈中若已存在该字符，则跳过
    if (stackMap[ch]) continue;

    // 单调栈结构，当发现栈顶元素比当前字符大，则出掉栈顶元素，保证单调栈递增
    while (stack.length > 0 && stack[stack.length - 1] > ch) {
      // 如果当前栈顶元素在剩余的字符串中已经不存在了，则不能删除
      if (countMap[stack[stack.length - 1]] === 0) break;

      // 出掉栈顶元素，保证单调栈递增
      const popCh = stack.pop();
      stackMap[popCh] = false;
    }
    // 入栈字符
    stack.push(ch);
    stackMap[ch] = true;
  }
  return stack.join('');
}