原文来自 我的个人博客

前言

拒绝摆烂ヾ(◍°∇°◍)ﾉﾞ

从今天开始（2023/02/12），定一个小目标，先刷个 300 道 Leetcode 题目（之前刷的不计入）。

当然作为一个小前端，我选择的语言是 TS，而且刷的题目的难度会偏中等一些，大概按照 简单3 中等6 困难1 这样的题型分布吧。嗯，目前是这么打算的。

本题 Github 地址：因为比较喜欢 vscode 的界面，而且方便调试，所以 AC 完就顺便提到 github 了，也算做一个记录吧。

本篇的题目是这个系列的第

1. NO.21：225. 用队列实现栈
2. NO.22：232. 用栈实现队列
3. NO.23：2073. 买票需要的时间
4. NO.24：面试题 03.02. 栈的最小值
5. NO.25：面试题 03.01. 三合一

1. 用队列实现栈

1.1 题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

进阶： 你能否仅用一个队列来实现栈。

1.2 解

因为在 js 中是没有栈和队列这种结构的，但是这两种结构我们都可以用数据来实现

class MyStack {
  data: number[] = [];
  constructor() {}

  push(x: number): void {
    this.data.push(x);
  }

  pop(): number {
    return this.data.pop()!;
  }

  top(): number {
    return this.data[this.data.length - 1];
  }

  empty(): boolean {
    return this.data.length === 0;
  }
}

2. 用栈实现队列

2.1 题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

• 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

2.2 解

这题和上一道差不多，直接上代码。

class MyQueue {
  data: number[] = []
  constructor() {}

  push(x: number): void {
    this.data.push(x)
  }

  pop(): number {
    return this.data.shift()!
  }

  peek(): number {
    return this.data[0]
  }

  empty(): boolean {
    return this.data.length === 0
  }
}

3. 买票需要的时间

3.1 题目描述

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到  队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。

返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

示例 1：

输入： tickets = [2,3,2], k = 2
输出： 6
解释： 
- 第一轮，队伍中的每个人都买到一张票，队伍变为 [1, 2, 1] 。
- 第二轮，队伍中的每个都又都买到一张票，队伍变为 [0, 1, 0] 。
位置 2 的人成功买到 2 张票，用掉 3 + 3 = 6 秒。

示例 2：

输入： tickets = [5,1,1,1], k = 0
输出： 8
解释：
- 第一轮，队伍中的每个人都买到一张票，队伍变为 [4, 0, 0, 0] 。
- 接下来的 4 轮，只有位置 0 的人在买票。
位置 0 的人成功买到 5 张票，用掉 4 + 1 + 1 + 1 + 1 = 8 秒。

提示：

• n == tickets.length
• 1 <= n <= 100
• 1 <= tickets[i] <= 100
• 0 <= k < n

3.2 解

将 tickets 当作一个队列，循环遍历 tickets，遍历的结束条件是 第 k 个人买完所有的票，
遍历的过程每个人的想买的票 -1，时间 +1，直到想买的票变为 0 时不再 +1。

function timeRequiredToBuy(tickets: number[], k: number): number {
  let count: number = 0;
  let i = 0;
  while (tickets[k] > 0) {
    if (tickets[i] > 0) {
      tickets[i]--;
      count++;
    }
    if (i < tickets.length - 1) i++;
    else i = 0
  }

  return count;
}

4. 面试题 03.02. 栈的最小值

4.1 题目描述

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

4.2 解：辅助栈

思路：设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

• 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
• 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

class MinStack {
  stack: number[] = [];
  min_stack: number[] = [Infinity];
  constructor() {}

  push(x: number): void {
    this.stack.push(x);
    this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x));
  }

  pop(): void {
    this.stack.pop();
    this.min_stack.pop();
  }

  top(): number {
    return this.stack[this.stack.length - 1];
  }

  getMin(): number {
    return this.min_stack[this.min_stack.length - 1];
  }
}

5. 面试题 03.01. 三合一

5.1 题目描述

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

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

提示：

• 0 <= stackNum <= 2

5.2 解

这题并没什么难的，就是在初始化时设置三个栈即可，出入栈要注意栈的 size

class TripleInOne {
  stack: [number[], number[], number[]] = [[], [], []];
  stackSize: number;
  constructor(stackSize: number) {
    this.stackSize = stackSize;
  }

  push(stackNum: number, value: number): void {
    this.stack[stackNum].length < this.stackSize ? this.stack[stackNum].push(value) : "";
  }

  pop(stackNum: number): number {
    return this.stack[stackNum].pop() ?? -1;
  }

  peek(stackNum: number): number {
    return this.stack[stackNum][this.stack[stackNum].length - 1] ?? -1;
  }

  isEmpty(stackNum: number): boolean {
    return this.stack[stackNum].length === 0;
  }
}