程序员面试金典 - 面试题 03.01. 三合一

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

三合一。描述如何只用一个数组来实现三个栈。

你应该实现 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]

题目思考

1. 需要定义哪些辅助变量?

解决方案

思路

• 由于已知每个栈的大小, 所以我们可以预留足够的空间来存储每个栈的元素, 即数组长度是 stackSize*3
• 然后可以定义每个栈的栈顶元素对应在数组中的下标, 以及栈的当前元素个数, 从而判断每个栈是否能 push 或 pop
• 具体做法如下:
  • [0, stackSize-1]区间存储下标为 0 的栈的元素, [stackSize, 2*stackSize-1]区间存储下标为 1 的栈的元素, 以此类推
  • 刚开始每个栈没有元素, 所以其栈顶元素下标初始化为[-1, stackSize-1, 2*stackSize-1]
  • push 的时候先判断是否为满, 不是的话将栈顶元素下标+1, 然后赋值
  • pop 和 peek 的时候先判断是否为空, 不是的话直接得到栈顶元素值, 然后 pop 需要额外将下标-1

复杂度

• 时间复杂度 O(1): 每个操作都是常数级别的时间复杂度
• 空间复杂度 O(N): 设每个栈的大小为 N, 需要预留 3*N 的空间

代码

class TripleInOne:
    def __init__(self, stackSize: int):
        # 预留空间, 记录每个栈的栈顶元素下标和元素个数
        self.stackSize = stackSize
        self.stack = [0] * stackSize * 3
        self.index = [-1, stackSize - 1, stackSize * 2 - 1]
        self.len = [0, 0, 0]

    def push(self, stackNum: int, value: int) -> None:
        if self.isFull(stackNum):
            return
        self.index[stackNum] += 1
        self.len[stackNum] += 1
        self.stack[self.index[stackNum]] = value

    def pop(self, stackNum: int) -> int:
        if self.isEmpty(stackNum):
            return -1
        res = self.stack[self.index[stackNum]]
        self.index[stackNum] -= 1
        self.len[stackNum] -= 1
        return res

    def peek(self, stackNum: int) -> int:
        if self.isEmpty(stackNum):
            return -1
        res = self.stack[self.index[stackNum]]
        return res

    def isFull(self, stackNum: int) -> bool:
        return self.len[stackNum] == self.stackSize

    def isEmpty(self, stackNum: int) -> bool:
        return self.len[stackNum] == 0

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊