LeetCode 面试题 03.01. 三合一

约 4 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 简单 程序员面试金典（第 6 版）
标签
数组 栈 设计

题目描述

✅ 面试题 03.01. 三合一

image-20260929004830790

题意分析

用一个数组实现编号为 0、1、2 的三个独立栈，每个栈容量固定为 stackSize。每次只操作指定栈：未满时允许入栈，满栈入栈忽略；空栈出栈或查看栈顶返回 -1，并支持判空。

解法：定长数组分段保存三个栈

核心思路

[!blue]

将数组前 3 * cap 个位置平均分成三段，每段保存一个栈。编号 k 的数据起点是 cap * k，再用数组末尾下标 3 * cap + k 保存这个栈当前的元素个数。数据和三个计数都存放在同一个数组中，因此总长度为 3 * cap + 3。

设某栈当前计数为 size，它的有效元素占据本段前 size 格，下一次入栈位置就是 起点 + size。只有 size < cap 时才写入并增加计数，既保证栈内顺序，也不会越过自己的数据段或覆盖计数槽位。

非空栈的栈顶位于 起点 + size - 1。pop 先将计数减一，再用新计数定位原栈顶并返回；peek 读取同一位置但不改变计数。由此后压入的元素总是先弹出，符合栈的后进先出规则。

弹出后无需把旧槽位清零，因为逻辑栈只由计数限定，下一次入栈会覆盖该位置。三个计数彼此独立，操作一个栈只修改它的数据段和计数，不能借用其他栈的空余容量。cap = 0 时所有计数都为零，入栈条件始终不成立，其他接口也能按空栈正常处理。

解题步骤

  1. 构造长度 3cap+3 的数组，计数初始化为零。
  2. push 检查未满，在起点+计数写入，再增加计数。
  3. pop 检查非空，先减少计数再读取原栈顶。
  4. peek 读取起点+计数-1，不改变计数；isEmpty 判断计数为零。

代码实现

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(cap+1)$；push、pop、peek、isEmpty 都只做固定次数的下标访问，为 $O(1)$。
  • 空间复杂度：$O(cap+1)$，一个长度为 3 * cap + 3 的数组。

关键点总结

[!green]

三个计数同时表示元素个数和下一次写入的段内偏移；数据与计数槽位的下标约定必须一致。

易错点总结

[!yellow]

  • cap=0 时所有 push 忽略，不能用 <= 判断未满。
  • peek 不得改变计数。
  • 三个栈分别检查自己的计数，不能借用其他栈空余容量。

相似题目

题目 难度 关联与区别
补充题 121. 用数组实现定长栈 中等 单个定长栈提供 push/pop 的计数模板，本题额外用分段偏移隔离三个栈。
622. 设计循环队列 中等 同样通过固定数组下标管理容量，队列循环复用首尾槽位，栈只维护顶部计数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/30237985
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！