LeetCode 316. Remove Duplicate Letters 2019-06-29

题目描述

给定一个仅包含小写字母的字符串,去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

tag

去重题 栈 贪心

样例

1
2
输入: "cbacdcbc"
输出: "acdb"

算法1

(贪心) O(n)
思路

栈中元素表示扫描到当前位置,当前出现的结果。
一个数组count记录字符串中字符出现的个数。
visit表示26个字符是否在当前的栈中。
对于每一个字符,先判断他是否在栈中,如果在栈中,那么直接去掉它。
如果不在栈中。 如果比栈末尾大,那么直接加在末尾。
如果比栈末尾小,这时候要弹出栈的末尾元素,弹出时要更新visit数组。
直到比栈末尾大这时候直接加上这个字符,并且维护visit。

复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
visit = [False] * 26
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1

res = []

for c in s:

count[ord(c) - ord('a')] -= 1
if visit[ord(c) - ord('a')]:
continue
# count[ord(res[-1]) - ord('a')] > 0 说明以后还有机会碰到它们
# 如果 = 0,则不许要pop
while res and res[-1] > c and count[ord(res[-1]) - ord('a')] > 0:
# 修改成False,不然以后碰到它们会跳过
visit[ord(res[-1]) - ord('a')]= False
res.pop()

res.append(c)
visit[ord(c) - ord('a')] = True


return ''.join(res)