leetcode 每日一题：316. 去除重复字母

一起刷题吧

输入：字符串
输出：去重后的字符串，要求保留原有字符的相对顺序，且得到的字符串最小
难度：中等
标签：栈、贪心

示例 1：
输入：s = "bcabc"
输出：“abc”

示例 2：
输入：s = "cbacdcbc"
输出：“acdb”

这个题个人认为是一个数学题，有一个基本原则：

比如当前字符串是 cb

当往后追加一个字符 a 时，此时 a 是比 c,b 都要小的。即显然越小的数值放在前面，最终的数值越小，那怎么决定前面的数值是否需要保留呢？（因为既要最小，也要全都有）

其实也很简单，只要前面的数值在后面仍然有可能出现即可

因此整个题目可以转化如下几步：

1. 依次遍历字符串的字符，同时用一个中间变量存储当前位置以前去重后得到的最小字符串
2. 如果当前字符串比前面字符串的结尾要小，则说明需要判断前面的字符串是否需要丢弃
3. 判断是否需要丢弃的标准即这个字符在之后是否还会出现

从上面的步骤可以看出，我们还需要知道每个字符串当前还剩余的次数。这里通过 python 的 collections 包下的 Counter 很容易得到。

参考代码如下：

from collections import Counter

# https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/ 和这个题一模一样


class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
 if not s:
     return s

 # 基本思想，首先统计每个字母出现的次数
 # 依次填入，每次可选择当前填入之后，前面的元素是丢弃还是保留
 # 如果前面的元素后面还有剩余，即剩余出现次数大于等于1，且前面的元素比当前元素都要大，则把前面的元素移除
 cs = Counter(s)
 stack = []
 uniq = set()
 for c in s:
     if c in uniq:
  cs[c] = cs[c] - 1
  continue
     # 因为还要达到去重的效果，所以这里最后一个判断需要加uniq
     while stack and cs[stack[-1]] >= 1 and stack[-1] >= c:
  uniq.remove(stack.pop())
     cs[c] = cs[c] - 1
     stack.append(c)
     uniq.add(c)
 return "".join(stack)

https://leetcode-cn.com/problems/remove-k-digits/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-5/