1. 三合一（用一个数组实现三个栈）
题目描述
实现一个数据结构，使用一个数组同时实现三个栈，支持 push(stackNum, value)、pop(stackNum)、peek(stackNum)、isEmpty(stackNum) 操作。
stackNum 表示栈编号（0、1、2），每个栈的容量固定。
解法二：数组按段切分法
最简单高效的方法是固定分区法：将一个数组平均切成三个区域，每个区域维护独立的栈指针。
- 核心思想：数组长度 =
stackSize * 3，第i个栈的起始索引为i * stackSize，使用一个sizes[]数组记录每个栈当前元素数。 - 优点：实现简单，O(1) 操作。
- 缺点：栈之间不能共享剩余空间，可能浪费存储。
实现细节：
push(stackNum, value)：检查是否满栈，未满则将元素放入对应栈区的下一个空位置。pop(stackNum)：检查是否空栈，非空则返回栈顶并减少计数。peek(stackNum)：直接返回对应栈顶元素。isEmpty(stackNum)：判断sizes[stackNum] == 0。
代码实现（Java 示例）：
class TripleInOne {
private int[] stackData; // 存储三个栈数据
private int stackSize; // 每个栈容量
private int[] sizes; // 每个栈当前元素数量
public TripleInOne(int stackSize) {
this.stackSize = stackSize;
stackData = new int[stackSize * 3];
sizes = new int[3]; // 初始化三个栈的大小
}
public void push(int stackNum, int value) {
if (sizes[stackNum] == stackSize) return; // 满栈
int index = getTopIndex(stackNum) + 1;
stackData[index] = value;
sizes[stackNum]++;
}
public int pop(int stackNum) {
if (isEmpty(stackNum)) return -1;
int topIndex = getTopIndex(stackNum);
int value = stackData[topIndex];
sizes[stackNum]--;
return value;
}
public int peek(int stackNum) {
if (isEmpty(stackNum)) return -1;
return stackData[getTopIndex(stackNum)];
}
public boolean isEmpty(int stackNum) {
return sizes[stackNum] == 0;
}
// 获取栈顶索引
private int getTopIndex(int stackNum) {
int offset = stackNum * stackSize;
int size = sizes[stackNum];
return offset + size - 1;
}
}
复杂度分析：
- 时间复杂度：O(1)（所有操作）
- 空间复杂度：O(stackSize × 3)（固定数组存储）
解法二：动态分区 + 环形数组 + 扩容搬移
- 核心思想：
- 数组视作环形结构（环状数组），头尾相连，避免固定边界限制。
- 每个栈维护开始索引、容量和当前大小。
- push 时，如果当前栈满，尝试扩容（向其他栈“借用”空间），通过搬移相邻栈的元素调整空间。
- 搬移操作基于环形数组顺序，保证所有栈的数据顺序连续。
- 关键点：
- 使用链式或结构体保存每个栈的边界信息。
- 搬移元素时，必须注意环绕情况和索引计算。
- 复杂度较固定分区法高，实现难度也大，但能更充分利用空间。
伪代码逻辑大致如下：
push(stackNum, val):
if 栈满:
扩容(stackNum)
插入元素，更新栈大小
扩容(stackNum):
计算需要扩容的空间
尝试搬移相邻栈元素以腾出空间
更新所有栈的起始位置和容量
总结
固定分区法实现简单、性能 O(1)，适合容量已知且均匀分配的场景；如果需要动态共享空间，可以使用灵活分区法（如循环队列 + 栈指针）来提升利用率，但实现更复杂。
2. 栈的最小值
题目描述
设计一个栈，除了支持常规的 push 和 pop 操作，还支持一个 min 函数，该函数能在 O(1) 时间内返回栈中的最小元素。要求所有操作的时间复杂度均为 O(1)。
输入：一系列 push、pop 和 min 操作
输出：min 操作返回当前栈中的最小值
解题思路
解法一：辅助栈存储当前最小值（推荐）
维护两个栈：
- 主栈
stack用于存储所有元素 - 辅助栈
minStack用于存储当前栈中的最小元素，栈顶始终保存当前最小值
关键逻辑：
每次 push 新元素时，将该元素与 minStack 栈顶的最小值比较，如果新元素更小或相等，则将它也压入 minStack。
每次 pop 时，如果弹出的元素等于 minStack 栈顶元素，也同步弹出 minStack。
这样，minStack 的栈顶元素就是当前主栈的最小值，实现 min 操作为 O(1)。
代码实现（Java 示例）
import java.util.Stack;
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
}
public void pop() {
if (stack.isEmpty()) return;
int top = stack.pop();
if (top == minStack.peek()) {
minStack.pop();
}
}
public int top() {
if (stack.isEmpty()) throw new RuntimeException("Stack is empty");
return stack.peek();
}
public int min() {
if (minStack.isEmpty()) throw new RuntimeException("Stack is empty");
return minStack.peek();
}
}
复杂度分析：
- 时间复杂度：
push,pop,min操作均为 O(1) - 空间复杂度：额外使用一个辅助栈存储最小值，最坏情况下空间复杂度为 O(n)，其中 n 是入栈元素个数
总结
辅助栈法是该问题的经典且最优解法，既能保证操作时间复杂度为 O(1)，又能简单直观地实现 min 功能。
适用于需要频繁查询当前最小值且性能要求高的栈操作场景。