Open zwzhome opened 3 years ago
思路: 第一步:因为要去重,因此通过hash表,统计每个字符出现的次数。 第二步:从头开始遍历字符串,依次入栈,如果cur不在stack中(在不在的判断,为了时间效率考虑,借用了hashset数据结构),执行入栈操作。如果cur < stack.top(),判断stack中比cur大的字符在hash表的计数中还有没有,还有的话,则可以出栈。 class Solution: def removeDuplicateLetters(self, s) -> int: stack = [] seen = set() remain_counter = collections.Counter(s)
for c in s: if c not in seen: while stack and c < stack[-1] and remain_counter[stack[-1]] > 0: seen.discard(stack.pop()) seen.add(c) stack.append(c) remain_counter[c] -= 1 return ''.join(stack)
作者:fe-lucifer 链接:https://leetcode-cn.com/problems/remove-duplicate-letters/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-4/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
思路: 第一步:因为要去重,因此通过hash表,统计每个字符出现的次数。 第二步:从头开始遍历字符串,依次入栈,如果cur不在stack中(在不在的判断,为了时间效率考虑,借用了hashset数据结构),执行入栈操作。如果cur < stack.top(),判断stack中比cur大的字符在hash表的计数中还有没有,还有的话,则可以出栈。 class Solution: def removeDuplicateLetters(self, s) -> int: stack = [] seen = set() remain_counter = collections.Counter(s)
作者:fe-lucifer 链接:https://leetcode-cn.com/problems/remove-duplicate-letters/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-4/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。