leetcode刷题指南之RemoveDuplicateLetters

编辑 | 刘凯旋

公众号 | 转载自 【编程与算法之美】

1.题目分析

给定一个字符串，删去重复字母使得每个字母只剩一个，并且字典序最小。

2.解题思路

最暴力的方法就是用dfs去搜索，记录哪些字母还没有出现，这个的复杂度是O(26!)的 ，显然不行。

暴力的做法只考虑了前一个条件，却没有考虑字典序最小这个也很关键的条件。想一下，字典序最小的情况，最优的肯定是字母较小的尽量靠前，字母大的尽量靠后。然而这个尽量，到底是什么程度呢？

考虑一个例子:

bcac，对于字母a来说，它显然不可能出现在首位，因为那意味着要把前面的bc删掉，而a的后面就不可能再有b了，而它却可以出现在c的前面，因为把它前面的c删掉之后，它的后面还有一个c。

因此，整体的算法就出来了：

我们一位一位处理字符串，假设处理到了第i位，并且已经得到当前最优的字符串s，如果第i位已经出现在s中，那么就没必要保留这一位了。

如果没有，考虑s的最后一个字母，如果它比最后第i位小，并且在第i位之后还出现了，那么就删掉，直到s为空或者s的最后一个字母不满足条件，把第i位放到最后。

举样例跑一遍：

cbacdcbc. 初始s为空。

i=0，s=c i=1，此时可以删掉c，s=b i=2，此时b可以删，s=a i=3，s=aci=4，此时s=acd i=5，此时s=acd i=6，此时s=acdb i=7，此时s=acdb

3.代码示例