LeetCode 面试题 03.06. 动物收容所

约 5 分钟
文章信息 3 个分类 2 个标签
分类
LeetCode 简单 程序员面试金典（第 6 版）
标签
设计 队列

题目描述

✅ 面试题 03.06. 动物收容所

image-20260929004907984

题意分析

收容所只接收猫和狗，animal[0] 是动物编号，animal[1] 为 0 表示猫、为 1 表示狗。领养可以指定种类，也可以不限种类，但都必须取符合条件的动物中最早入所的一只；没有可领养的动物时返回 [-1, -1]。

解法：两类 FIFO 队列比较入所序号

核心思路

[!blue]

指定种类领养需要找到该类最早入所的动物，所以分别用两条先进先出队列保存猫和狗。只用一条总队列时，指定种类可能要从中间寻找并删除；分成两队后，指定领养就能直接取对应队首。

不限种类领养还需要比较两队的先后。每次入所都附加一个全局递增的 sequence，猫和狗共用这个计数器。队列保存原编号和内部入所序号，比较时间只看内部序号，返回结果仍使用原编号和种类。

为什么只比较队首就够了？某只动物若不是本类队首，前面一定还有一只同类动物比它更早，它就不可能是全所最早者。因此全局最早动物只能是猫队首或狗队首，选择序号较小的一只即可。

若一队为空，直接从另一队领养；两队都为空时，转交给任一种类的出队方法，也会得到失败结果。每次出队都只移除队首，剩下动物的相对入所顺序保持不变，后续操作仍满足同样规则。

解题步骤

  1. 构造两条空队列和入所序号。
  2. enqueue 根据种类选择队列，保存动物编号与当前序号，再递增序号。
  3. 指定领养从对应队首取出，组合成 [原编号, 种类]；队列为空则返回 [-1, -1]。
  4. dequeueAny 先排除空队情况，两队都非空时比较队首序号，调用较早一侧的出队方法。

代码实现

class AnimalShelf {
    private Deque<long[]>[] q = new Deque[2];
    private long sequence;

    public AnimalShelf() {
        Arrays.setAll(q, k -> new ArrayDeque<>());
    }

    public void enqueue(int[] animal) {
        q[animal[1]].offer(new long[] {
            animal[0],
            sequence++
        });
    }

    public int[] dequeueAny() {
        if (q[0].isEmpty() || (!q[1].isEmpty() && q[1].peek()[1] < q[0].peek()[1])) {
            return dequeueDog();
        }

        return dequeueCat();
    }

    public int[] dequeueDog() {
        return q[1].isEmpty()
                ? new int[] {
                    -1,
                    -1
                }
                : new int[] {
                    (int) q[1].poll()[0],
                    1
                };
    }

    public int[] dequeueCat() {
        return q[0].isEmpty()
                ? new int[] {
                    -1,
                    -1
                }
                : new int[] {
                    (int) q[0].poll()[0],
                    0
                };
    }
}

type arrival struct {
    id    int
    order int64
}

type AnimalShelf struct {
    q        [2][]arrival
    sequence int64
}

func Constructor() AnimalShelf {
    return AnimalShelf{}
}

func (this *AnimalShelf) Enqueue(animal []int) {
    this.q[animal[1]] = append(this.q[animal[1]], arrival{animal[0], this.sequence})
    this.sequence++
}

func (this *AnimalShelf) DequeueAny() []int {
    if len(this.q[0]) == 0 || (len(this.q[1]) > 0 && this.q[0][0].order > this.q[1][0].order) {
        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.id,
        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.id,
        0,
    }
}

复杂度分析

  • 时间复杂度：入队均摊 O(1)，出队查询 O(1)。
  • 空间复杂度：按累计入所数 N 给出 O(N) 上界；逻辑队列只保存未领养者，但底层数组容量不保证随出队立即缩小。

关键点总结

[!green]

分类队列负责保留各自的入所顺序，统一序号负责比较不同种类的先后；两类需求都只需要访问队首或队尾。

易错点总结

[!yellow]

  • 不要用动物编号比较到达先后。
  • 两队都空也应返回 [-1,-1]。
  • 返回原动物编号和种类，不返回内部序号。

相似题目

题目 难度 关联与区别
622. 设计循环队列 中等 复用 FIFO 的队首队尾语义，本题在两条分类队列之间按时间合并选择。
23. 合并 K 个升序链表 困难 选择下一项时只比较各路队首，本题只有两路且排序键为入所顺序。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/88517834
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！