1081.不同字符的最小子序列

链接：1081.不同字符的最小子序列
难度：Medium
标签：栈、贪心、字符串、单调栈
简介：返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。

题解 1 - typescript

• 编辑时间：2021-07-30
• 执行用时：176ms
• 内存消耗：46.1MB
• 编程语言：typescript
• 解法介绍：单调栈。

function smallestSubsequence(s: string): string {
  const map: Record<string, number> = {};
  for (const c of s) map[c] = (map[c] ?? 0) + 1;
  const stack: string[] = [];
  const set = new Set<string>();
  const toNum = (c: string) => c.codePointAt(0)! - 'a'.codePointAt(0)!;
  for (const c of s) {
    if (set.has(c)) {
      map[c]--;
      continue;
    }
    while (
      stack.length &&
      toNum(stack[stack.length - 1]) > toNum(c) &&
      map[stack[stack.length - 1]] > 0
    ) {
      console.log(set);
      set.delete(stack.pop()!);
    }
    stack.push(c);
    set.add(c);
    map[c]--;
  }
  return stack.join('');
}