File tree Expand file tree Collapse file tree
Stack/316.Remove-Duplicate-Letters Expand file tree Collapse file tree Original file line number Diff line number Diff line change 22
33总体思想是贪心法，用stack做辅助。基本方法仍然是用手头的字符尽量维持一个递增字符序列，因为递增序列意味着字典序最小。
44
5- 首先， 在维护栈的过程中，遇到已经用过的字符就跳过。比如当前待处理的字符是c，而当前的栈已经有c了， 意味着什么呢？因为栈在维护着一个递增序列，说明c后面的字符要比c大。如果舍弃已经用过的c ，那么必将导致后续的大字符前移，使得构建的栈内的单词字典序会变小 。
5+ 在维护栈的过程中，第一个原则是： 遇到已经用过的字符就跳过。举个例子，假设当前待处理的字符是c，而发现当前栈里已经有c了， 意味着什么呢？因为栈在维护着一个递增序列，说明栈里c后面的字符要比c大。如果舍弃已经栈里的c ，那么必将导致后续的大字符前移，使得构建的栈内的单词字典序会变大 。
66
7- 接下来， 如果遇到非递增的字符，则大致方向就是退栈-- 处理掉一些栈顶元素，使得新加入的仍能保持递增。但需要注意，如果待退栈处理的字符在后面还有出现的机会，就放心退栈，扔到后面去考虑；如果后面已经没有再出现的机会，则保留这个栈顶元素同时结束退栈。所以需要一个Hash表来实时记录每个字符剩下来还会出现几次，也就是说每遍历一个字符，就把Map[ s[ i]] --.
7+ 第二个原则： 如果遇到非递增的字符，则大致方向就是退栈， 处理掉一些栈顶元素，使得新加入的仍能保持递增。但需要注意，如果待退栈处理的字符在后面还有出现的机会，就放心退栈，扔到后面去考虑；如果后面已经没有再出现的机会，则保留这个栈顶元素同时结束退栈。所以需要一个Hash表来实时记录每个字符剩下来还会出现几次，也就是说每遍历一个字符，就把Map[ s[ i]] --.
88
99本题和1081. Smallest Subsequence of Distinct Characters一模一样。
1010
1111
12- [ Leetcode Link] ( https://leetcode.com/problems/remove-duplicate-letters )
12+ [ Leetcode Link] ( https://leetcode.com/problems/remove-duplicate-letters )
You can’t perform that action at this time.
0 commit comments