网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的面试题 03.01. 三合一，难度为 Easy。
三合一。描述如何只用一个数组来实现三个栈。
你应该实现 push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum) 方法。
stackNum表示栈下标，value表示压入的值。
构造函数会传入一个stackSize参数，代表每个栈的大小。
示例1:
输入： ["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"] [[1], [0, 1], [0, 2], [0], [0], [0], [0]] 输出： [null, null, null, 1, -1, -1, true] 说明：当栈为空时`pop, peek`返回-1，当栈满时`push`不压入元素。 复制代码
示例2:
输入： ["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"] [[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]] 输出： [null, null, null, null, 2, 1, -1, -1] 复制代码
二维数组解法
题目只要求我们使用「一个数组」来实现栈，并没有限制我们使用数组的维度。
因此一个简单的做法是，建立一个二维数组 datadata 来做。
二维数组的每一行代表一个栈，同时使用一个 locationslocations 记录每个栈「待插入」的下标。
代码：
class TripleInOne { int N = 3; // 3 * n 的数组，每一行代表一个栈 int[][] data; // 记录每个栈「待插入」位置 int[] locations; public TripleInOne(int stackSize) { data = new int[N][stackSize]; locations = new int[N]; } public void push(int stackNum, int value) { int[] stk = data[stackNum]; int loc = locations[stackNum]; if (loc < stk.length) { stk[loc] = value; locations[stackNum]++; } } public int pop(int stackNum) { int[] stk = data[stackNum]; int loc = locations[stackNum]; if (loc > 0) { int val = stk[loc - 1]; locations[stackNum]--; return val; } else { return -1; } } public int peek(int stackNum) { int[] stk = data[stackNum]; int loc = locations[stackNum]; if (loc > 0) { return stk[loc - 1]; } else { return -1; } } public boolean isEmpty(int stackNum) { return locations[stackNum] == 0; } } 复制代码
- 时间复杂度：所有的操作均为 O(1)O(1)。
- 空间复杂度：O(k * n)O(k∗n)。k 为我们需要实现的栈的个数，n 为栈的容量。
一维数组解法
当然了，我们也能使用一个一维数组来做。
建立一个长度为 3 * stackSize3∗stackSize 的数组，并将 3 个栈的「待插入」存储在 locationslocations 数组。
代码：
class TripleInOne { int N = 3; int[] data; int[] locations; int size; public TripleInOne(int stackSize) { size = stackSize; data = new int[size * N]; locations = new int[N]; for (int i = 0; i < N; i++) { locations[i] = i * size; } } public void push(int stackNum, int value) { int idx = locations[stackNum]; if (idx < (stackNum + 1) * size) { data[idx] = value; locations[stackNum]++; } } public int pop(int stackNum) { int idx = locations[stackNum]; if (idx > stackNum * size) { locations[stackNum]--; return data[idx - 1]; } else { return -1; } } public int peek(int stackNum) { int idx = locations[stackNum]; if (idx > stackNum * size) { return data[idx - 1]; } else { return -1; } } public boolean isEmpty(int stackNum) { return locations[stackNum] == stackNum * size; } } 复制代码
- 时间复杂度：所有的操作均为 O(1)O(1)。
- 空间复杂度：O(k * n)O(k∗n)。k 为我们需要实现的栈的个数，n 为栈的容量。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
