【刷题日记】316. 去除重复字母

本次刷题日记的第 42 篇，力扣题为：316. 去除重复字母 ，中等

一、题目描述：

乍一看这个题是什么感受，又是一个中等题，但是题目内容极少的一道题，我电脑一个屏就可以装下了，我们肯定可以解决

二、这道题考察了什么思想？你的思路是什么？

来看这题给我们展示了哪些重要的信息呢？

• 题目给出的字符串中，只包含 26 个字母，且顺序是未知的
• 题目要求我们按照去除字符串中重复的字符，且要保证字典序是最小的，还要求我们这些字母的相对位置需要正确

看到这里，是不是觉得这个题要求好多呀，不过没有关系，我们就像满足客户需求一样，分析好了可行性之后，再来满足需求

我们来看题目的要求，需要保证咱们的字母相对位置要是和题目给出的字符串相对位置要一样，那么我们其实就可以想到，应该是需要遍历题目给出的字符串的，这样做才是比较很简单的

那么对于去除重复的字符，这个也就更简单了，但是其实并不纯粹，因为我们去除的重复字母是需要有方法的，并不是随便就去掉了，因为，题目要求咱们保证字典序还要是最小的

那么这个需要如何思考呢？

第一要保证顺序，第二要去掉重复的字符，那么我们是否可以使用栈来保证顺序性呢？

如何保证字典序呢？字典序，我们是不是只需要保证 前一个字母大于后一个字母的时候，咱们就要把前一个字母干掉？

咱们在遍历的过程中，保证好如上 3 点，那么一直遍历到字符串结尾，我们就可以得到答案了

大体思路我们可以这样来保证：

• 使用一个 helper 数组来存放 26 个字母中，每个字符现在还剩余的个数，当有字符入栈的时候，这个 hepler 数组对应的字符数量就减去 1 个
• 拿一个切片来模拟栈，遍历字符串的时候，校验当前字符是否小于栈顶元素，若是，那么就去掉栈顶元素，并将当前元素入栈
• 拿一个hash表来记录，某个字母是否已经存在与栈中了

按照上述思路来进行编码的话，我们应该都能实现了吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，

• 这里需要注意，对于已经存在与栈里面的字符，我们就会再去校验他是否比栈顶的元素小了，因为按照之前的逻辑和流程，这种就需要跳过了
• 另外对于校验到当前的元素比栈顶的小的时候，如果校验到栈顶的元素已经只有这一个了，那么我们也是需要跳过的

func removeDuplicateLetters(s string) string {
   // 定义一个数组，作为hash表，记录字符的剩余个数
    help := [26]int{}
    // 记录当前字符串中中每个字符的出现次数
    for _, ch := range s {
        help[ch-'a']++
    }
    // 用一个切片来模拟栈
    stack := []byte{}
    // 用于记录是否在栈中
    inStack := [26]bool{}
    for i := range s {
        ch := s[i]
        // 如果 ch 字符不在 栈中
        if !inStack[ch-'a'] {
            // 当前的栈切片是有值的，且当前的字符是小于栈顶字符的
            for len(stack) > 0 && ch < stack[len(stack)-1] {
                last := stack[len(stack)-1] - 'a'
                if help[last] == 0 {
                    break
                }
                // 去掉栈顶的元素
                stack = stack[:len(stack)-1]
                // 设置该字符不在栈中
                inStack[last] = false
            }
            stack = append(stack, ch)
            inStack[ch-'a'] = true
        }
        help[ch-'a']--
    }
    return string(stack)
}

按照如上实现的话，相信很容易就能看明白这个单调栈处理的方式吧，分析清楚了的话还是很简单的

四、总结：

就上述编码来看，这里的时间复杂度是多少呢，这个应该是非常明显的，因为我们只遍历了一次题目给出的字符串，所以时间复杂度是 O(n)

空间复杂度是 O(∣Σ∣) ，这个的含义在这里实际上是 26 ，因为咱们的字母个数只有 26 个，咱们引入的额外的空间是 26 个 int

原题地址：316. 去除重复字母

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~