LeetCode 补充题 141. 字符流中第一个不重复的字符
题目描述
[!green]
牛客原题： ✅ 补充题 141. 字符流中第一个不重复的字符
字符流逐个插入 ASCII 字符。
每次查询返回目前只出现一次的字符中最早插入的那个；不存在时返回
#。
示例 1：
输入：
依次插入的字符 = "google"，每次插入后查询一次
输出：["g","g","g","#","l","l"]
解释： 插入第二个g后，g和o都重复，因此返回 #；插入l后，它成为最早的唯一字符。
提示：
- 每次插入一个 ASCII 字符。
- 按目前整个输入前缀查询，不存在唯一字符时返回
#。
题意分析
查询需要同时知道“只出现一次”和“最早插入”两个条件。计数可以判断是否重复，队列则保留各字符首次出现顺序；字符一旦重复，在只插入的流中就永远不会重新唯一。
解法：三态计数与候选队列
核心思路
[!blue]
count[c]只保存 0、1、2 三种状态，其中 2 表示至少两次。首次插入才把字符放到队尾，后续插入只把状态饱和到 2，避免长字符流中的计数溢出。查询时，反复删除队首已重复的字符。只要队首仍唯一，它就是全部剩余候选中首次出现最早的一个；队内较后位置的失效字符暂时不影响答案，可以延后处理。
每个 ASCII 字符至多入队和出队一次，连续查询不会重复扫描已经淘汰的前缀。候选为空返回
#；Java 用队列删除队首，Go 只推进head，避免搬移元素。
解题步骤
- 字符首次出现时入候选队列，计数饱和到 2 表示重复。
- 查询时不断移除队头已经重复的字符。
- 队列为空返回 #，否则返回队头唯一字符。
代码实现
class FirstUnique {
private final int[] count = new int[128];
private final ArrayDeque<Character> queue = new ArrayDeque<>();
public void insert(char c) {
if (count[c] == 0) {
queue.addLast(c);
}
count[c] = Math.min(2, count[c] + 1);
}
public char first() {
while (!queue.isEmpty() && count[queue.peekFirst()] != 1) {
queue.removeFirst();
}
return queue.isEmpty() ? '#' : queue.peekFirst();
}
}
type FirstUnique struct {
count [128]int
queue []byte
head int
}
func (s *FirstUnique) Insert(c byte) {
if s.count[c] == 0 {
s.queue = append(s.queue, c)
}
s.count[c] = min(2, s.count[c]+1)
}
func (s *FirstUnique) First() byte {
for s.head < len(s.queue) && s.count[s.queue[s.head]] != 1 {
s.head++
}
if s.head == len(s.queue) {
return '#'
}
return s.queue[s.head]
}
复杂度分析
- 时间复杂度：n次插入/查询总时间 $O(n)$。
- 空间复杂度：固定ASCII字母表下空间 $O(1)$。
关键点总结
[!green]
一个字符变成重复后不会再次唯一，候选只需入队一次，后续失效可以等它到队首时再处理。
易错点总结
[!yellow]
重复后不能重新变成唯一；不是返回当前字符串中的最小字母；Java实例化FirstUnique，Go零值即可使用。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 387. 字符串中的第一个唯一字符 | 简单 | 从静态统计再扫描扩展到在线输入，队列保留第一次出现顺序，并延迟清除已重复候选。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！