LeetCode 面试题 03.01. 三合一

2026-03-28 HGNULB 约 8 分钟

文章信息 3 个分类 3 个标签

分类

题目描述

✅ 面试题 03.01. 三合一

题意分析

要设计一个类，用一个一维数组同时承载三个互相独立的栈，对外暴露 push、pop、peek、isEmpty 四个接口，每次调用都带上栈号 stackNum。

构造函数给出的 stackSize 是每个栈的容量上限，这是最关键的一条约束：容量固定意味着每个栈占用的下标区间可以事先算死，不需要动态扩容，也不会互相挤占。这一点直接排除了「三个栈共享空间、谁用得多谁占得多」的复杂方案。

另一条约束来自异常语义：栈满时 push 静默丢弃（不报错、不覆盖），栈空时 pop 与 peek 返回 -1 而不是抛异常。所以每个操作的第一步都必须是状态检查，且检查依据只能是「当前栈已存了多少个元素」。

边界：stackSize 可能为 0，此时任何 push 都应被丢弃、任何 pop 都返回 -1；三个栈的读写必须彼此隔离，对 0 号栈的操作绝不能影响 1 号栈的栈顶。

解法：数组扫描

核心思路

先想暴力：类里放三个 ArrayList 或三个独立数组，逻辑最简单，但题面明确要求「用一个数组」实现，这个写法直接违题；而且真到了内存受限的场景，三份对象头与三次扩容都是浪费。瓶颈在于我们把「三个栈」当成了三份存储，其实它们只是同一块连续内存上的三段。

观察：容量固定，所以第 k 个栈的数据天然可以放在下标区间 $[k \cdot cap,\ (k+1) \cdot cap)$ 上，栈内第 t 个元素的位置就是 cap * k + t。三段互不重叠，隔离性由下标公式本身保证，不需要任何运行时判断。

还差一样东西：每个栈当前的元素个数。既然题目只允许一个数组，就把这三个计数器也塞进同一个数组的尾部——这正是代码把长度开成 cap * 3 + 3 的原因，前 cap * 3 格存数据，最后 3 格当栈顶指针。

于是不变量确定为：stk[cap * 3 + k] 恒等于第 k 个栈的当前元素个数，同时也是该栈下一个元素要写入的段内偏移；stk[cap * k + t] 存放第 k 个栈自底向上第 t 个元素。所有四个接口都只是这两条不变量的直接读写。

解题步骤

构造：记下 cap = stackSize，开长度为 cap * 3 + 3 的数组。多出来的 3 格必须放在尾部而不是头部，否则数据段的起始下标就要额外偏移，公式会变复杂且更易错。

isEmpty(k)：直接判 stk[cap * 3 + k] == 0。这个方法被 pop 与 peek 复用，把空判定收敛到一处，避免三处各写一遍不一致。

push(k, v)：先判 stk[cap * 3 + k] < cap，满了就什么都不做——题目要求静默丢弃，所以这里没有 else 分支。未满则先按当前计数写值 stk[cap * k + 计数] = v，再把计数加一。顺序是「先用后加」，因为计数值本身就是下一个空位的偏移。

pop(k)：先判空返回 -1；否则先把计数减一，再按新计数取值。顺序是「先减后取」，与 push 恰好镜像——减完之后计数指向的正是刚才的栈顶。

peek(k)：不改计数，所以取值时要手动补上 -1：stk[cap * k + 计数 - 1]。这个 -1 是 peek 与 pop 唯一的写法差异，也是最容易漏的地方。

以 stackSize = 1 走一遍，依次调用 push(0, 1)、push(0, 2)、pop(0)、pop(0)。构造后 cap = 1，数组长度为 6，下标 0、1、2 分别是三个栈的数据格，下标 3、4、5 是三个栈的计数器，初始全为 0。

push(0, 1)：计数 stk[3] = 0 小于 cap = 1，写 stk[1 * 0 + 0] = stk[0] = 1，计数变为 1。push(0, 2)：计数 stk[3] = 1 不小于 1，栈已满，静默返回，数组不变。pop(0)：非空，计数先减到 0，取 stk[0] = 1 返回。pop(0)：计数为 0，判空成立，返回 -1。整串输出是 [null, null, null, 1, -1]，与题面示例一致。

代码实现

class TripleInOne {
    private int cap;
    private int[] stk;

    public TripleInOne(int stackSize) {
        cap = stackSize;
        // 前 cap * 3 格存数据，末尾 3 格存三个栈的元素个数。
        stk = new int[cap * 3 + 3];
    }

    public void push(int stackNum, int value) {
        if (stk[cap * 3 + stackNum] < cap) {
            stk[cap * stackNum + stk[cap * 3 + stackNum]] = value;
            ++stk[cap * 3 + stackNum];
        }
    }

    public int pop(int stackNum) {
        if (isEmpty(stackNum)) {
            return -1;
        }
        // 先减后取：减完之后计数正好指向原栈顶。
        --stk[cap * 3 + stackNum];
        return stk[cap * stackNum + stk[cap * 3 + stackNum]];
    }

    public int peek(int stackNum) {
        return isEmpty(stackNum) ? -1 : stk[cap * stackNum + stk[cap * 3 + stackNum] - 1];
    }

    public boolean isEmpty(int stackNum) {
        return stk[cap * 3 + stackNum] == 0;
    }
}

type TripleInOne struct {
    cap int
    stk []int
}

func Constructor(stackSize int) TripleInOne {
    // 前 stackSize * 3 格存数据，末尾 3 格存三个栈的元素个数。
    return TripleInOne{stackSize, make([]int, stackSize*3+3)}
}

func (this *TripleInOne) Push(stackNum int, value int) {
    if this.stk[this.cap*3+stackNum] < this.cap {
        this.stk[this.cap*stackNum+this.stk[this.cap*3+stackNum]] = value
        this.stk[this.cap*3+stackNum]++
    }
}

func (this *TripleInOne) Pop(stackNum int) int {
    if this.IsEmpty(stackNum) {
        return -1
    }
    // 先减后取：减完之后计数正好指向原栈顶。
    this.stk[this.cap*3+stackNum]--
    return this.stk[this.cap*stackNum+this.stk[this.cap*3+stackNum]]
}

func (this *TripleInOne) Peek(stackNum int) int {
    if this.IsEmpty(stackNum) {
        return -1
    }
    return this.stk[this.cap*stackNum+this.stk[this.cap*3+stackNum]-1]
}

func (this *TripleInOne) IsEmpty(stackNum int) bool {
    return this.stk[this.cap*3+stackNum] == 0
}

复杂度分析

时间复杂度：四个接口均为 $O(1)$，每次调用只做常数次下标计算与数组读写，没有任何搬移或遍历。

空间复杂度：$O(stackSize)$，整个对象只持有一个长度为 stackSize * 3 + 3 的数组，与调用次数无关。

关键点总结

容量固定是「分段定址」能成立的前提：段起点 cap * k 写死在公式里，隔离性就不需要任何运行时检查，这是本题最值得说出口的设计取舍。

把三个栈顶指针也塞进同一个数组，是对「只用一个数组」这条约束的正面回应；面试时先说清楚这块布局，再写代码，逻辑会顺很多。

push 的「先写后加」与 pop 的「先减后取」互为镜像，peek 因为不动计数所以要补 -1；把栈顶指针的语义固定为「元素个数」而不是「栈顶下标」，三个方法的写法就能一次对齐。

空判、满判统一走计数器，把 isEmpty 抽成公共方法供 pop 与 peek 复用，能消除三处重复判断带来的不一致风险。

面试官常追问「如果不限定每个栈容量、要求空间自适应怎么办」：标准答案是改成柔性分割，栈满时整体搬移并重新分配区间，或者用链式栈；能主动对比两种方案的取舍才算答完整。

易错点总结

数组只开 cap * 3 长度：stackSize = 1 时首次 push(0, 1) 访问 stk[3] 读计数，直接下标越界。

计数器放数组开头：stackSize = 2 → 数据段起点仍按 cap * k 算，0 号栈的第一个元素写进了计数格，isEmpty(0) 立刻返回错误结果。

push 写成「先加后写」：stackSize = 2，push(0, 5) → 计数先变成 1，值被写到 stk[1]，stk[0] 空着；随后 pop(0) 减到 0 取 stk[0]，返回垃圾值 0 而不是 5。

pop 写成「先取后减」：stackSize = 2，push(0, 5) 后 pop(0) → 计数为 1 时取 stk[1]，取到的是未写入的空位，返回 0。

peek 忘了减一：push(0, 5) 后 peek(0) → 计数为 1，取 stk[1]，返回 0 而不是 5。

peek 顺手把计数减了：push(0, 5) 后连续两次 peek(0) → 第一次返回 5 并把计数清零，第二次直接返回 -1，peek 变成了 pop。

栈满时抛异常或覆盖栈顶：stackSize = 1，push(0, 1) 后 push(0, 2) → 题目要求静默丢弃，覆盖会让随后的 pop(0) 返回 2 而不是 1。

栈空时返回 0 而不是 -1：stackSize = 1 时直接 pop(0) → 返回 0 与「栈里真的存了一个 0」无法区分，判题按 -1 校验，直接失败。

stackSize = 0 未被主逻辑覆盖：push(0, 1) 时计数 0 不小于 cap = 0，正确路径是丢弃；若把满判写成 <= 就会写入 stk[0]，而 stk[0] 此时正是 0 号栈的计数格，计数被污染。

相似题目

题目	难度	考察点
155. 最小栈	中等	同为栈的设计题，但要额外维护历史最小值，考的是辅助栈或差值编码
面试题 03.02. 栈的最小值	简单	与 155 同题，可用一个栈存差值把辅助空间省掉
232. 用栈实现队列	简单	用受限结构模拟另一种结构，核心是两栈倒腾与均摊分析
面试题 03.04. 化栈为队	简单	与 232 同题，注意倒栈时机决定单次操作最坏耗时
225. 用队列实现栈	简单	反方向模拟，单队列做法要在入队后把前面的元素轮转到队尾
622. 设计循环队列	中等	同样是定长数组加下标运算，但用取模实现环形，空满判定要额外留位
面试题 03.05. 栈排序	中等	借助辅助栈维持有序性，考的是插入时的搬移策略而非空间布局