总体思想是贪心法,用stack做辅助。基本方法仍然是用手头的字符尽量维持一个递增字符序列,因为递增序列意味着字典序最小。
在维护栈的过程中,第一个原则是:遇到已经用过的字符就跳过。举个例子,假设当前待处理的字符是c,而发现当前栈里已经有c了,意味着什么呢?因为栈在维护着一个递增序列,说明栈里c后面的字符要比c大。如果舍弃已经栈里的c,那么必将导致后续的大字符前移,使得构建的栈内的单词字典序会变大。
第二个原则:如果遇到非递增的字符,则大致方向就是退栈,处理掉一些栈顶元素,使得新加入的仍能保持递增。但需要注意,如果待退栈处理的字符在后面还有出现的机会,就放心退栈,扔到后面去考虑;如果后面已经没有再出现的机会,则保留这个栈顶元素同时结束退栈。所以需要一个Hash表来实时记录每个字符剩下来还会出现几次,也就是说每遍历一个字符,就把Map[s[i]]--.
本题和1081. Smallest Subsequence of Distinct Characters一模一样。