Manjusaka

09-26 leetcode 0316

链接 316. Remove Duplicate Letters

题目

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

题解

这题其实是一个单调栈的应用

1. 遍历一次字符串，将每个字符出现的位置和字符串中的位置做一下索引。重复的字符在遍历结束后字符位置是最后一个字符的位置
2. 用一个栈和一个 hash 表来维护结果
3. 遍历字符串，当字符没有出现过时判断栈的最后一个字符串是否比当前字符大，如果比当前字符大且栈的最后一个字符在后面还会出现，那么我们就可以将栈的最后一个字符弹出，反复循环吗，直到栈中不会出现满足条件的字符，然后将当前字符入栈

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        index = {char: i for i, char in enumerate(s)}
        stack = []
        visited = set()
        for i, value in enumerate(s):
            if value not in visited:
                while stack and stack[-1] > value and index[stack[-1]] > i:
                    visited.remove(stack.pop())
                stack.append(value)
                visited.add(value)
        return "".join(stack)