316. 去除重复字母

316. 去除重复字母

原始题目链接:https://leetcode-cn.com/problems/remove-duplicate-letters/

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
316. 去除重复字母
解题思路:

思路和402题的思路一样,使用栈来存储和比较相邻字符的入栈出栈条件,具体实现看代码和注释。

代码实现:

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # 使用一个栈,存储符合条件的字符
        stack = []

        # 统计字符串中各个字符的个数
        char_map = collections.Counter(s)

        for c in s:
            # 开始入栈出栈的逻辑:判断当前字符是否在栈中
            # c不在栈中,就需要判断是否满足入栈的逻辑
            if c not in stack:
                # 栈不空才能比较,当前字符c没次和栈中的上一个入栈字符比较(stack[-1])
                # 并且上一个入栈字符的个数不能为空,空的话不能再出栈了,否则会漏掉改字符
                # 如果当前字符c小于其上一个入栈字符即相邻字符,就将相邻字符出栈
                while stack and c < stack[-1] and char_map[stack[-1]] > 0:
                    stack.pop()
                
                # c不在栈中就让c入栈
                stack.append(c)
            
            # 字符的个数减1
            char_map[c] -= 1
        
        return "".join(stack)

参考文献:
https://leetcode-cn.com/problems/remove-duplicate-letters/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-4/

上一篇:【C语言学习】单链表的创建、增删、交换、排序


下一篇:[docker] 构建镜像