LeetCode 面试题 03.06. 动物收容所
目录
题目描述
题意分析
要设计一个收容所：动物按先来后到入所，领养者可以选择「要最早入所的那只，不挑种类」，也可以指定「只要狗」或「只要猫」。入所的动物用二元组表示，第一维是唯一编号，第二维是种类（0 表示猫、1 表示狗）。
最关键的约束是题面明确给出的：编号
number严格递增。这句话把「谁更早入所」从一个需要额外时间戳的问题，变成了一次数值比较——编号小的一定更早。识别出这一点，就不必再自己维护计数器或入所序号。第二条信号来自三种出队方式：指定种类的出队要求同种类内部保持先进先出，不挑种类的出队要求全局先进先出。前者说明按种类分桶是自然的，后者说明分桶之后必须能 $O(1)$ 地比较两个桶的队首谁更早——而队首恰好就是各自桶里最小的编号。
边界：某一类空了、两类都空了，指定出队与任意出队都必须返回
[-1, -1]而不是抛异常；某一类空时，任意出队要能自动落到另一类上，不能因为一次空判就直接返回失败。
解法：设计处理
核心思路
朴素做法是所有动物塞进一条队列。任意出队确实是 $O(1)$，但指定要狗时得从队首往后线性扫描找第一只狗，还要把它从链表中间摘掉，单次操作退化成 $O(n)$。瓶颈很清楚：一条队列只能维护一种顺序，而题目要同时维护「全局顺序」和「同种类顺序」两种视图。
观察到全局顺序其实可以从同种类顺序推出来：把猫和狗分成两条队列，各自内部先进先出；全局最早的那只，必然是两条队列队首中编号较小的那一只——因为它比本队列后面的都早，也比另一队列的队首早，而另一队列的队首又比该队列其余的都早。于是两条队列的队首就构成了全局最早的候选集，比一次即可定案。
维护的状态因此是：
q[0]存所有在所猫的编号、q[1]存所有在所狗的编号，两条队列都按入所顺序排列。不变量是「每条队列内部编号递增，且队首是该种类中最早入所的个体」；入队只往尾部追加、出队只从头部取走，这条不变量自然守恒。用种类值直接当数组下标（
q[animal[1]]），可以把「是猫还是狗」的分支从代码里彻底消掉，入队退化成一行。
解题步骤
- 构造：开两条队列
q[0]、q[1]，下标即种类编码。用数组而不是两个命名字段，是为了让enqueue能直接用种类值寻址。enqueue(animal)：q[animal[1]].offer(animal[0])。队列里只存编号不存种类——种类信息已经由「它在哪条队列里」表达了，再存一遍是冗余。dequeueCat/dequeueDog：先判对应队列是否为空，空则返回[-1, -1]；否则弹出队首编号，拼上固定的种类值返回。返回值必须是二元组，种类那一位由方法自己写死，不需要查。dequeueAny：分两种情况汇成一个条件——猫队为空，或者狗队非空且狗队首编号更小，这两种情况都走dequeueDog，否则走dequeueCat。把「另一队为空」和「另一队更晚」合并进同一个分支，是这段代码简洁的关键；两队皆空时会落到dequeueCat，由它返回[-1, -1]，无需额外判断。- 复用而非重写：
dequeueAny不直接操作队列，而是转调另外两个方法，这样空判与返回值格式只有一份实现。以题面示例走一遍：依次
enqueue([0, 0])、enqueue([1, 0])、enqueue([2, 1])，然后dequeueDog()、dequeueCat()、dequeueAny()。三次入队后
q[0] = [0, 1]（两只猫）、q[1] = [2]（一只狗）。dequeueDog()：狗队非空，弹出 2，返回[2, 1]，此时q[1]变空。dequeueCat()：猫队非空，弹出 0，返回[0, 0]，q[0] = [1]。dequeueAny()：猫队非空，狗队为空导致「狗队非空且更早」不成立，整个条件为假，转调dequeueCat()，弹出 1 返回[1, 0]。输出序列[[2, 1], [0, 0], [1, 0]]与示例一致。
代码实现
class AnimalShelf {
// q[0] 存猫的编号，q[1] 存狗的编号，下标即种类。
private Deque<Integer>[] 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};
}
}
type AnimalShelf struct {
// q[0] 存猫的编号，q[1] 存狗的编号，下标即种类。
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}
}
复杂度分析
- 时间复杂度：四个接口均为 $O(1)$，入队是尾部追加，三种出队最多做两次队首查看与一次弹出，都是常数操作。
- 空间复杂度：$O(n)$，
n为当前在所动物数，两条队列合起来恰好存下每只在所动物的编号，出队即释放。
关键点总结
- 一条数据结构只能维护一种顺序，需要同时支持多种视图时就按维度分桶，再用「各桶队首构成全局候选集」的性质把跨桶比较压到常数级——这是多队列设计题的通用套路。
- 题面给出的「编号严格递增」是可以直接当时间戳用的免费信息；面试时要主动指出这一点，说明自己没有多此一举地再造一个自增计数器。
- 用种类编码直接当数组下标，能把 if-else 分支变成寻址，代码短且不易写歪；这类「用数据本身索引」的技巧在状态机、方向数组里同样适用。
- 把
dequeueAny实现成对另外两个方法的转调，空判与返回格式只写一遍，是接口类设计题里降低出错面的常规手段。- 面试官容易追问「如果编号不保证递增怎么办」：那就得自己维护一个自增序号随动物一起入队，比较时比序号而非编号；答出这条替换方案说明理解了「比较的到底是什么」。
易错点总结
- 只用一条队列并线性查找：连续入队 1000 只猫后
dequeueDog()→ 每次都要扫过全部猫才发现没有狗，单次操作退化成线性，大批量调用直接超时。dequeueAny里漏掉「另一队为空」的分支：enqueue([0, 0])后dequeueAny()→ 直接比较两队队首时对空的狗队取队首，抛出空指针或越界。- 比较写反成「编号大的更早」：
enqueue([0, 0])、enqueue([1, 1])后dequeueAny()→ 返回[1, 1]，把最晚入所的狗当成了最早的。- 比较写成
<=或>=无所谓：编号严格递增所以两队首绝不会相等，但若把它误当成可以相等而额外加了同值处理分支，就是白写的死代码，反而掩盖了「编号唯一」这条关键前提。- 队列里连种类一起存但取值时下标写错：
enqueue([2, 1])后dequeueDog()→ 返回[1, 1]，把种类当成了编号。- 两类皆空时返回空数组：初始状态直接
dequeueAny()→ 判题按[-1, -1]校验，返回[]或null都算错。dequeueCat里返回的种类位写成 1：enqueue([0, 0])后dequeueCat()→ 返回[0, 1]，编号对但种类错。- 入队时不按种类分桶，统一 append 到
q[0]：enqueue([0, 1])后dequeueDog()→ 狗队始终为空，永远返回[-1, -1]。- Go 里用
this.q[1] = this.q[1][1:]出队却又在别处保留了旧切片头：同一条队列被两个切片变量引用时，一侧出队不会反映到另一侧，dequeueAny与dequeueDog会看到不同的队首。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 622. 设计循环队列 | 中等 | 同为队列设计，但重点在定长数组的环形下标与空满判定 |
| 232. 用栈实现队列 | 简单 | 用受限结构模拟队列，考的是两栈倒腾时机与均摊复杂度分析 |
| 面试题 03.04. 化栈为队 | 简单 | 与 232 同题，注意只在出栈为空时才整体倒栈 |
| 225. 用队列实现栈 | 简单 | 反方向模拟，单队列解法靠入队后轮转把新元素顶到队首 |
| 面试题 03.01. 三合一 | 简单 | 同样是多结构共存，但共享的是一个定长数组，靠分段定址而非分桶 |
| 155. 最小栈 | 中等 | 也要额外维护一份辅助视图，不过维护的是极值而非到达顺序 |
| 面试题 03.05. 栈排序 | 中等 | 靠辅助栈维持有序，出队顺序由值大小而非入队时间决定 |