目录：LeetCode 索引

1 验证栈序列（LeetCode 946）

给定 pushed 和 popped 两个序列（值不重复），判断 popped 是否可能是空栈上 push/pop 操作的结果。

• 输入 pushed = [1,2,3,4,5], popped = [4,5,3,2,1] → true
• 输入 pushed = [1,2,3,4,5], popped = [4,3,5,1,2] → false（1 不能在 2 之前弹出）

知识点

1. 栈的特点：后进先出（LIFO / FILO）；
2. Python 判断 list 为空可直接作为条件的布尔值：
   l = [] if l: # 空 list 为 False print('not empty') else: print('empty')

算法过程

1. 定义 stack 列表模拟栈，index 指示 popped 当前元素位置（初始 0）；
2. 遍历 pushed 依次入栈；
3. 每入栈一个元素，循环检查：栈非空且栈顶元素 == popped[index]，则出栈并 index+1，持续到栈空或栈顶不匹配；
4. 判断最终 stack 是否为空：为空说明 popped 是可能的出栈顺序。

Python3 版

Python 中模拟栈可用 list 或 collections.deque。用 list 时注意用 len(stack) >= 1 判断非空、用 stack[-1] 取栈顶，避免越界异常。

class Solution: def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool: length = len(popped) stack = [] index = 0 for number in pushed: stack.append(number) # 栈顶元素 == 下一个要 pop 的元素则出栈 # len(stack) >= 1 保证 stack[-1] 不越界 while(len(stack) >= 1 and index < length and stack[-1] == popped[index]): stack.pop() index += 1 # 最终栈为空，说明 popped 是可能的出栈序列 return len(stack) == 0

参考：Python 中的栈

---

2 队列的最大值 剑指 Offer 59-II

定义队列并实现 max_value、push_back、pop_front，要求三个函数均摊时间复杂度 O(1)。队列为空时 pop_front 和 max_value 返回 -1。

知识点

1. 队列：FIFO；
2. 双端队列：两边都可出入。

思路

用普通队列保存入队元素，用单调递减双端队列保存最大值候选：队列头到队尾非严格递减，头部始终存当前最大值。入队时从尾部弹出比新值小的元素。

import queue class MaxQueue: def __init__(self): # 有序双端队列：队头到队尾非严格递减，队头始终存最大元素 self.sorted_double_ended_queue = queue.deque() # 普通队列存出入元素 self.queue = queue.Queue() def max_value(self) -> int: # deque 可直接用 if 判断非空（queue.Queue 不行，必须用 empty()） if not self.sorted_double_ended_queue: return -1 # 取队头元素（popleft 后 appendleft 写回，保持 O(1) 且不丢元素） front = self.sorted_double_ended_queue.popleft() self.sorted_double_ended_queue.appendleft(front) return front def push_back(self, value: int) -> None: # 从双端队列尾部开始，只要比 value 小就弹出（保持单调递减） while self.sorted_double_ended_queue: tail = self.sorted_double_ended_queue.pop() if tail >= value: self.sorted_double_ended_queue.append(tail) break self.sorted_double_ended_queue.append(value) self.queue.put(value) def pop_front(self) -> int: if self.queue.empty(): return -1 front = self.queue.get() # 出队元素等于最大值时，从双端队列移除队头 if self.sorted_double_ended_queue and self.max_value() == front: self.sorted_double_ended_queue.popleft() return front

注意点：

• queue.Queue 是否为空必须用 empty() 判断，if q: 永远为 True；deque 则可以直接 if 判断；
• push_back 中 tail >= value 才停止弹出，是为了正确处理重复的最大值。

---

3 第一个只出现一次的字符 剑指 Offer 50

在字符串 s 中找出第一个只出现一次的字符，没有则返回单空格。s 只包含小写字母，长度 ≤ 50000。

• s = "abaccdeff" → 返回 "b"
• s = "" → 返回 " "

知识点

队列和集合；Python 中用 list 模拟队列、dict 模拟集合（value 置 True）。

算法过程

1. 异常检查：不是字符串直接返回 ' '；
2. 两个对象：queue 暂存只出现一次的字符，isExisting 记录已出现过的字符；
3. 遍历字符串：
   • 字符已在 queue → 不是唯一字符，从 queue 删除；
   • 不在 queue 且不在 isExisting → 放入 queue，并在 isExisting 记录（防止重复入队）；
4. queue 空返回 ' '，否则返回 queue[0]。

为什么需要 isExisting：如 aababc，queue 中字符被删除后若不记录，第三个 a 从 queue 看是新字符会被再入队，产生”幻觉”，导致误判。

class Solution: def firstUniqChar(self, s: str) -> str: if not isinstance(s, str): return ' ' isExisting = {} queue = [] for c in s: # 已在 queue 中则说明出现不止一次，删除 if c in queue: queue.remove(c) else: # 不在 isExisting 中才入队，防止已被删除的字符再次入队 if not c in isExisting: isExisting[c] = True queue.append(c) if len(queue) == 0: return ' ' return queue[0]

复杂度：remove 为 O(n)，整体 O(n²)，但字符串仅 26 小写字母时行为可接受；更优解法可用 count 数组记录字符出现次数后二次扫描。