前言
持续更新了
正文
问题来源
本问题来自leetcode上的316题。
问题描述
给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1:
输入: "bcabc"
输出: "abc"
示例 2:
输入: "cbacdcbc"
输出: "acdb"
分析：
先遍历字符串，记录每个元素出现次数
接着元素挨个入栈，
维持栈的核心要素是：保持栈内所有元素都小于即将进栈的元素，即字典序
如果不满足，则需要把栈内元素出栈，直到满足要求为止
func removeDuplicateLetters(s string) string {
exist := make([]bool, 26)
stack := make([]byte, 0)
count := make([]int, 26)
for i := 0; i < len(s); i++ {
count[s[i]-'a']++
}
for i := 0; i < len(s); i++ {
index := s[i]-'a'
if exist[index] {
count[index]--
continue
}
// 出栈的核心判断要素：
// 1. 栈里有元素
// 2. 栈顶元素大于当前元素c
// 3. 栈顶元素在后续出现
for len(stack) > 0 && stack[len(stack)-1] > s[i] && count[stack[len(stack)-1]-'a'] > 0 { // 循环出栈判断
exist[stack[len(stack)-1]-'a'] = false
stack = stack[:len(stack)-1]
}
stack = append(stack, s[i])
count[index]--
exist[index] = true
}
return string(stack)
}
总结：
勤思考。
结语
不管怎么样好好加油。
