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
27
28
29
30
31
32
33
// @Title: 去除重复字母 (Remove Duplicate Letters)
// @Author: 15816537946@163.com
// @Date: 2020-12-20 11:42:01
// @Runtime: 0 ms
// @Memory: 2.1 MB
func removeDuplicateLetters(s string) string {
	left := [26]int{}
	for _, ch := range s {
		left[ch-'a']++
	}

	stack := []byte{}
	inStack := [26]bool{}

	for i := range s {
		ch := s[i] // 必须的, string 里 range 读出的 类型是 rune
		if !inStack[ch-'a'] {
			for len(stack) > 0 && ch < stack[len(stack)-1] {
				last := stack[len(stack)-1] - 'a'
				if left[last] == 0 {
					break
				}
				stack = stack[:len(stack)-1]
				inStack[last] = false
			}
			stack = append(stack, ch)
			inStack[ch-'a'] = true
		}
		left[ch-'a']--
	}
	return string(stack)
}