316.去除重复字母

链接：316.去除重复字母
难度：Medium
标签：栈、贪心、字符串、单调栈
简介：给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

题解 1 - typescript

• 编辑时间：2020-12-20
• 执行用时：116ms
• 内存消耗：41.9MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/remove-duplicate-letters/solution/qu-chu-zhong-fu-zi-mu-by-leetcode-soluti-vuso/)。

function removeDuplicateLetters(s: string): string {
  const vis = new Array(26).fill(0);
  const num = _.countBy(s);
  const getCode = (c: string) => c.codePointAt(0)! - 'a'.codePointAt(0)!;
  const stack = new Array();
  let c: string;
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (!vis[getCode(ch)]) {
      while (stack.length > 0 && (c = stack[stack.length - 1]) > ch) {
        if (num[c] > 0) {
          vis[getCode(c)] = 0;
          stack.pop();
        } else {
          break;
        }
      }
      vis[getCode(ch)] = 1;
      stack.push(ch);
    }
    num[ch]--;
  }
  return stack.join('');
}

题解 2 - typescript

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

function removeDuplicateLetters(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
    ) {
      set.delete(stack.pop()!);
    }
    stack.push(c);
    set.add(c);
    map[c]--;
  }
  return stack.join('');
}