doocs/leetcode 题解精讲：面试题 03.06 动物收容所（Animal Shelter）双队列实现

示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载导读本文围绕 doocs/leetcode 仓库中《程序员面试金典第 6 版》系列题解 lcci/03.06.Animal Shelter 展开深度剖析动物收容所这道队列设计题在只收容猫、狗且严格先进先出的规则下如何实现enqueue、dequeueAny、dequeueDog、dequeueCat四个操作。读完本文你将掌握双队列 队首编号比较的核心解法理解其 $O(1)$ 时间、$O(n)$ 空间复杂度的由来并能在 Python、Java、C、Go、TypeScript、Rust、Swift 七种语言中直接落地实现。题目定义数据模型与操作语义题目出自《程序员面试金典第 6 版》面试题 03.06仓库中的题目原文位于 lcci/03.06.Animal Shelter/README.md英文版见 README_EN.md。收容所规则收容所只收容狗与猫严格遵守先进先出FIFO原则。收养人只能收养所有动物中最老按进入收容所的时间长短而定的一只或者可以挑选猫或狗此时必须收养**该类动物中最老**的一只收养人不能自由挑选具体某一只动物。方法签名与参数格式需要实现的数据结构支持四个操作方法入参 / 返回语义enqueue(animal)animal[0]为动物编号animal[1]为种类0猫1狗将动物送入收容所dequeueAny()返回[动物编号, 动物种类]收养全局最老的动物dequeueDog()返回[动物编号, 1]收养最老的狗dequeueCat()返回[动物编号, 0]收养最老的猫补充约束若没有可收养的动物dequeue*方法统一返回[-1, -1]收容所的最大容量为 20000。示例验证示例 1依次执行enqueue([0,0])猫 0、enqueue([1,0])猫 1随后dequeueCat、dequeueDog、dequeueAny输入 [AnimalShelf, enqueue, enqueue, dequeueCat, dequeueDog, dequeueAny] [[], [[0, 0]], [[1, 0]], [], [], []] 输出 [null, null, null, [0, 0], [-1, -1], [1, 0]]两只猫依次入所dequeueCat领走编号 0 的猫此时没有狗dequeueDog返回[-1,-1]最后dequeueAny领走剩下的最老动物——编号 1 的猫。示例 2依次执行enqueue([0,0])、enqueue([1,0])、enqueue([2,1])狗 2随后dequeueDog、dequeueCat、dequeueAny输入 [AnimalShelf, enqueue, enqueue, enqueue, dequeueDog, dequeueCat, dequeueAny] [[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []] 输出 [null, null, null, null, [2, 1], [0, 0], [1, 0]]三只动物按编号 0、1、2 的时间次序入所其中狗只有编号 2。dequeueDog领走[2,1]dequeueCat领走猫中最老的编号 0dequeueAny时只剩编号 1 的猫返回[1,0]。可见时间最老的判定完全由进入顺序决定与动物编号大小一致。解题思路为什么单一队列不够用核心矛盾如果只用一条 FIFO 队列dequeueAny可以直接取队首——它天然就是全局最老的动物。但dequeueDog/dequeueCat要求跳过另一种动物取出本类最老的一只这在单队列中需要从队首扫描并临时搬移元素无法做到 $O(1)$。双队列设计题目解法给出关键观察猫与狗的相对到达次序各自独立。因此可以准备两个队列q[0]存放猫的编号按入所时间先后排列q[1]存放狗的编号按入所时间先后排列。由于动物编号随时间递增编号越小意味着越早入所、越老因此每个队列的队首就是该类的最老成员。仓库题解原文lcci/03.06.Animal Shelter/README.md对四个操作的定义如下enqueue设动物编号为 $i$、种类为 $j$将 $i$ 入队到q[j]即按种类分流存储dequeueAny若q[0]为空或者q[1]非空且q[1]队首编号小于q[0]队首编号则调用dequeueDog否则调用dequeueCat——即比较两队队首取更小者更老者dequeueDog若q[1]为空返回[-1,-1]否则弹出队首编号并返回[编号, 1]dequeueCat若q[0]为空返回[-1,-1]否则弹出队首编号并返回[编号, 0]。这一设计的巧妙之处在于dequeueAny不需要维护额外的全局时间戳用队首编号大小比较就等价于比较到达时间从而让所有操作都保持在常数时间内完成。复杂度结论题解明确给出以上操作的时间复杂度均为 $O(1)$空间复杂度为 $O(n)$其中 $n$ 为收容所中动物的数量。多语言实现仓库源码逐语言解读仓库为该题提供了 7 种语言的完整可运行实现对应文件统一位于 lcci/03.06.Animal Shelter/ 目录Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.swift。下面逐一解读。Python3Solution.pyclass AnimalShelf: def __init__(self): self.q [deque(), deque()] def enqueue(self, animal: List[int]) - None: i, j animal self.q[j].append(i) def dequeueAny(self) - List[int]: if not self.q[0] or (self.q[1] and self.q[1][0] self.q[0][0]): return self.dequeueDog() return self.dequeueCat() def dequeueDog(self) - List[int]: return [-1, -1] if not self.q[1] else [self.q[1].popleft(), 1] def dequeueCat(self) - List[int]: return [-1, -1] if not self.q[0] else [self.q[0].popleft(), 0]实现要点Python 使用collections.deque作为双端队列popleft()保证从队首弹出是 $O(1)$dequeueAny中not self.q[0]处理猫队列为空的情况q[1][0] q[0][0]用于比较两队队首的新旧。需注意self.q [deque(), deque()]中q[0]是猫队列、q[1]是狗队列与题目约定animal[1]中0代表猫、1代表狗严格对应。JavaSolution.javaclass AnimalShelf { private DequeInteger[] q new Deque[2]; public AnimalShelf() { Arrays.setAll(q, k - new ArrayDeque()); } public void enqueue(int[] animal) { q[animal[1]].offer(animal[0]); } public int[] dequeueAny() { if (q[0].isEmpty() || (!q[1].isEmpty() q[1].peek() q[0].peek())) { return dequeueDog(); } return dequeueCat(); } public int[] dequeueDog() { return q[1].isEmpty() ? new int[] {-1, -1} : new int[] {q[1].poll(), 1}; } public int[] dequeueCat() { return q[0].isEmpty() ? new int[] {-1, -1} : new int[] {q[0].poll(), 0}; } }实现要点Java 用Deque接口 ArrayDeque实现offer队尾入队、poll队首出队、peek只读队首均为 $O(1)$。Arrays.setAll(q, k - new ArrayDeque())一次性初始化两个队列简洁且不易遗漏。题目明确允许使用 Java 内置的 LinkedList 数据结构这里选用ArrayDeque是更高效的双端队列实现同样满足要求。CSolution.cppclass AnimalShelf { public: AnimalShelf() { } void enqueue(vectorint animal) { q[animal[1]].push(animal[0]); } vectorint dequeueAny() { if (q[0].empty() || (!q[1].empty() q[1].front() q[0].front())) { return dequeueDog(); } return dequeueCat(); } vectorint dequeueDog() { if (q[1].empty()) { return {-1, -1}; } int dog q[1].front(); q[1].pop(); return {dog, 1}; } vectorint dequeueCat() { if (q[0].empty()) { return {-1, -1}; } int cat q[0].front(); q[0].pop(); return {cat, 0}; } private: queueint q[2]; };实现要点C 直接使用标准库queueint数组q[2]front()读取队首、pop()移除队首。dequeueDog/dequeueCat需要先front()取值再pop()因为pop()不返回元素——这是与 Python/Java 版本写法上的主要差异。GoSolution.gotype AnimalShelf struct { q [2][]int } func Constructor() AnimalShelf { return AnimalShelf{} } func (this *AnimalShelf) Enqueue(animal []int) { this.q[animal[1]] append(this.q[animal[1]], animal[0]) } func (this *AnimalShelf) DequeueAny() []int { if len(this.q[0]) 0 || (len(this.q[1]) 0 this.q[0][0] this.q[1][0]) { return this.DequeueDog() } return this.DequeueCat() } func (this *AnimalShelf) DequeueDog() []int { if len(this.q[1]) 0 { return []int{-1, -1} } dog : this.q[1][0] this.q[1] this.q[1][1:] return []int{dog, 1} } func (this *AnimalShelf) DequeueCat() []int { if len(this.q[0]) 0 { return []int{-1, -1} } cat : this.q[0][0] this.q[0] this.q[0][1:] return []int{cat, 0} }实现要点Go 版本用切片[2][]int模拟队列入队append出队通过this.q[1] this.q[1][1:]丢弃队首元素等价于队首弹出。注意DequeueAny中的比较条件写作this.q[0][0] this.q[1][0]猫队首编号大于狗队首编号则领狗与题解中的逻辑表述等价只是比较方向不同。TypeScriptSolution.tsclass AnimalShelf { private q: number[][] [[], []]; constructor() {} enqueue(animal: number[]): void { const [i, j] animal; this.q[j].push(i); } dequeueAny(): number[] { if (this.q[0].length 0 || (this.q[1].length 0 this.q[0][0] this.q[1][0])) { return this.dequeueDog(); } return this.dequeueCat(); } dequeueDog(): number[] { if (this.q[1].length 0) { return [-1, -1]; } return [this.q[1].shift()!, 1]; } dequeueCat(): number[] { if (this.q[0].length 0) { return [-1, -1]; } return [this.q[0].shift()!, 0]; } }实现要点TS 用二维数组number[][]存放两个队列push入队、shift()出队。shift()的返回值类型是number | undefined这里用非空断言!告知编译器在队列非空的前提下一定存在队首元素。RustSolution.rsuse std::collections::VecDeque; struct AnimalShelf { q: [VecDequei32; 2], } impl AnimalShelf { fn new() - Self { AnimalShelf { q: [VecDeque::new(), VecDeque::new()], } } fn enqueue(mut self, animal: Veci32) { self.q[animal[1] as usize].push_back(animal[0]); } fn dequeue_any(mut self) - Veci32 { if self.q[0].is_empty() || (!self.q[1].is_empty() self.q[1].front().unwrap() self.q[0].front().unwrap()) { self.dequeue_dog() } else { self.dequeue_cat() } } fn dequeue_dog(mut self) - Veci32 { if self.q[1].is_empty() { vec![-1, -1] } else { let dog self.q[1].pop_front().unwrap(); vec![dog, 1] } } fn dequeue_cat(mut self) - Veci32 { if self.q[0].is_empty() { vec![-1, -1] } else { let cat self.q[0].pop_front().unwrap(); vec![cat, 0] } } }实现要点Rust 使用VecDeque提供双端队列语义push_back入队尾、pop_front出队首。由于animal[1]是i32用作数组下标前需as usize转型。front().unwrap()/pop_front().unwrap()依赖队列非空的前置条件这与各语言版本中先判空再取值的逻辑一致。SwiftSolution.swiftclass AnimalShelf { private var q: [[Int]] Array(repeating: [], count: 2) init() { } func enqueue(_ animal: [Int]) { q[animal[1]].append(animal[0]) } func dequeueAny() - [Int] { if q[0].isEmpty || (!q[1].isEmpty q[1].first! q[0].first!) { return dequeueDog() } return dequeueCat() } func dequeueDog() - [Int] { return q[1].isEmpty ? [-1, -1] : [q[1].removeFirst(), 1] } func dequeueCat() - [Int] { return q[0].isEmpty ? [-1, -1] : [q[0].removeFirst(), 0] } }实现要点Swift 用[[Int]]数组存两个队列append入队、removeFirst()出队。q[1].first!的强制解包同样依赖判空逻辑。七种语言的实现思路完全同构只是在各自语言的容器 API 上做了对应映射。复杂度与边界情况分析时间复杂度enqueue入队操作 $O(1)$dequeueDog/dequeueCat判空 弹出队首$O(1)$dequeueAny仅比较两个队首peek/front/ 索引访问不涉及扫描$O(1)$。因此四个操作均为常数时间与队列中动物数量无关。空间复杂度双队列最多同时容纳 $n$ 只动物容量上限 20000每个动物编号只存储一次空间为 $O(n)$。关键边界情况某一类队列为空dequeueAny必须能回退到非空队列。例如示例 1 中只有猫时dequeueAny应返回猫而非[-1,-1]——判断条件not self.q[0]猫队列为空时直接走dequeueDog分支显然不对题解中的条件写法是猫队空或狗队非空且狗队首更老时领狗否则领猫两者都空时任一分支都会走到对应dequeue*并返回[-1,-1]两类都为空任一dequeue*均返回[-1,-1]编号大小即时间序由于入所编号单调递增队首编号比较天然等价于到达时间比较无需额外维护全局计数器。从双队列看这类双数据结构设计范式动物收容所的双队列方案本质上是用两个同构容器分别维护两个维度的有序性再用一个轻量比较规则合并决策的设计范式。它和以下经典题目思路同源最小栈面试题 03.02 Min Stack主栈之外再维护一个单调栈用第二个容器记录历史最小值用两个栈实现队列剑指 Offer 面试题 09 用两个栈实现队列入栈、出栈分工模拟 FIFO 语义。共同点是单容器无法同时满足全部操作约束时不引入复杂数据结构而是用第二个简单容器分摊职责牺牲少量空间换取所有操作 $O(1)$。这也是面试中常被考察的优化思路——先说明单队列为何不行再给出双队列设计最后用两个示例逐步验证即可构成完整且清晰的解题叙述。总结面试题 03.06 动物收容所是考察队列理解与以空间换时间思维的经典题目。核心结论可归纳为三点数据建模动物用[编号, 种类]表示0猫、1狗收容所容量上限 20000算法设计q[0]、q[1]两个队列分别按到达序存猫、狗编号dequeueAny通过比较两队队首编号选出全局最老者复杂度四个操作均摊 $O(1)$ 时间、$O(n)$ 空间。仓库中 lcci/03.06.Animal Shelter/ 目录提供了七种语言的完整实现与题目原文README.md可作为刷题与面试准备的直接参考。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐OpenDesign 中复刻 Airtable 设计系统白画布、深海军蓝与蓝色调阴影的完整规范与实践OpenDesign 中复刻 Airtable 设计系统白画布、深海军蓝与蓝色调阴影的完整规范与实践 导读 本文围绕 OpenDesign 仓库中内置的「Ai示例工程教程doocs/leetcode 题解精读面试题 01.04 回文排列Palindrome Permutation的奇偶性判定与双解法实现doocs/leetcode 题解精读面试题 01.04 回文排列Palindrome Permutation的奇偶性判定与双解法实现 导读 「回文排列」示例工程教程深入doocs/leetcode剑指Offer题解精讲深入doocs/leetcode剑指Offer题解精讲 本文深入分析了doocs/leetcode项目中剑指Offer题解的精髓系统性地将经典面试题目按照技示例工程教程上一篇Wand-Enhancer终极指南打造你的个性化游戏修改器平台下一篇WarcraftHelper终极指南免费解锁魔兽争霸3 144Hz高帧率体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考