LeetCode 316. 去除重复字母

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 316. 去除重复字母

思路分析

思路描述

参考代码

func removeDuplicateLetters(s string) string {
	var stack []byte
	lastOccurrence := make(map[byte]int)
	visited := make(map[byte]bool)
	// 记录每个字符的最后出现位置
	for i := 0; i < len(s); i++ {
		lastOccurrence[s[i]] = i
	}
	for i := 0; i < len(s); i++ {
		c := s[i]
		// 如果字符已经在栈中，跳过
		if visited[c] {
			continue
		}
		// 如果栈不为空，并且当前字符比栈顶字符小，
		// 且栈顶字符在后面还会出现，则出栈
		for len(stack) > 0 && c < stack[len(stack)-1] && i < lastOccurrence[stack[len(stack)-1]] {
			delete(visited, stack[len(stack)-1])
			stack = stack[:len(stack)-1]
		}
		// 将当前字符入栈
		stack = append(stack, c)
		visited[c] = true
	}
	return string(stack)
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/78861367