前言
原文来自我的个人博客
1. 认识栈结构
- 栈是一种 后进先出（LIFO） 的数据结构
- 在
js中没有栈，但我们可以用 数组或链表 实现栈的所有功能 栈的常用操作:
1. `push（入栈）` 2. `pop（出栈）` 3. `peek（返回栈顶元素）` 4. `isEmpty（判断是否为空栈）` 5. `size（返回栈里元素个数）`
栈的结构示意图
# 2. 实现栈结构的封装
实现栈结构有两种比较常见的方式：
- 基于 数组 实现
基于 链表 实现
链表也是一种数据结构， js 中没有自带链表结构，后续会写关于链表的文章，本章先使用数组来实现。
2.1 基于数组 v1 版
// 封装一个栈
class ArrayStack {
// 定义一个数组，用于存储元素
private data: any[] = [];
constructor(data: any[]) {
this.data = data || [];
}
// 实现栈中相关的操作方法
// push 方法：将一个元素压入栈中
push(element: any): void {
this.data.push(element);
}
// pop方法：将栈顶的元素弹出栈（返回出去，并且从栈顶移除）
pop(): any {
return this.data.pop();
}
// peek方法：返回栈顶元素
peek(): any {
return this.data[this.data.length - 1];
}
// isEmpty方法：判断栈是否为空
isEmpty(): boolean {
return this.data.length === 0;
}
// size放法：返回栈里元素个数
size(): number {
return this.data.length;
}
}测试：
const as = new ArrayStack();
as.push(1);
as.push(2);
as.pop();
as.push(3);
console.log(as); // ArrayStack { data: [ 1, 3 ] }2.2 使用泛型重构 v2 版
上面我们已经基于数组实现了一个栈结构，其实是已经可以使用了。
但是有个小问题就是并不能很好的限制栈中元素的类型，原因就是我们用了太多 any，这种情况下我们可以使用范型来限制
// 封装一个栈
class ArrayStack<T = any> {
// 定义一个数组，用于存储元素
private data: T[] = [];
constructor(data: T[]) {
this.data = data || [];
}
// 实现栈中相关的操作方法
// push 方法：将一个元素压入栈中
push(element: T): void {
this.data.push(element);
}
// pop方法：将栈顶的元素弹出栈（返回出去，并且从栈顶移除）
pop(): T | undefined {
return this.data.pop();
}
// peek方法：返回栈顶元素
peek(): T | undefined {
return this.data[this.data.length - 1];
}
// isEmpty方法：判断栈是否为空
isEmpty(): boolean {
return this.data.length === 0;
}
// size放法：返回栈里元素个数
size(): number {
return this.data.length;
}
}测试：
const as = new ArrayStack<number>();
as.push(1);
as.push('2'); // ✖️ 类型“string”的参数不能赋给类型“number”的参数。
as.push(2);
as.pop();
as.push(3);
console.log(as);3. 实战一：有效的括号
这道题来自 Leetcode 上的第 20 道题，难度：简单
3.1 题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入： s = "()"
输出： true示例 2：
输入： s = "()[]{}"
输出： true示例 3：
输入： s = "(]"
输出： false提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
3.2 题目分析
这是一道非常经典的关于 栈 的面试题
- 我们只需要维护一个栈结构
遍历给定的字符串
s：- 遇到
[、{、(这三种符号时将它们压入栈， - 遇到
]、}、)这三种符号时就取出栈顶元素与之对比，如果不能够组成有效括号则函数直接返回false，如果能则进入下个循环比较 - 知道循环结束，判断栈中元素如果为空则表示字符串有效，反之则无效
- 遇到
3.3 解一：栈
function isValid(s: string): boolean {
const stack = new ArrayStack<string>();
for (let i = 0; i < s.length; i++) {
const c = s[i];
switch (c) {
case "{":
stack.push("}");
break;
case "[":
stack.push("]");
break;
case "(":
stack.push(")");
break;
default:
if (stack.pop() !== c) return false;
}
}
return stack.isEmpty();
}4. 实战二：下一个更大元素 I
这道题是来自 Leetcode 上的第 496 道题，难度：简单
4.1 题目描述
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x **大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：
输入： nums1 = [4,1,2], nums2 = [1,3,4,2].
输出： [-1,3,-1]
解释： nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。示例 2：
输入： nums1 = [2,4], nums2 = [1,2,3,4].
输出： [3,-1]
解释： nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
提示：
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 104nums1和nums2中所有整数 互不相同nums1中的所有整数同样出现在nums2中
4.2 解一：暴力
这道题可以通过暴力法解决。
思路：
- 双重循环遍历
nums1和nums2两个数组 - 在第一层遍历
nums1循环中，找出nums1[i]对应 在nums2中的下标位置pos - 从
pos + 1位置开始遍历 nums2 数组，查找比nums[i]大的数字
代码：
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
let res: number[] = [];
for (let i = 0; i < nums1.length; i++) {
let pos: number = 0;
for (let j = 0; j < nums2.length; j++) {
if (nums2[j] === nums1[i]) {
pos = j;
break;
}
}
if (pos === nums2.length - 1) res.push(-1);
for (let j = pos + 1; j < nums2.length; j++) {
if (nums2[j] > nums1[i]) {
res.push(nums2[j]);
break;
}
if (j >= nums2.length - 1) res.push(-1);
}
}
return res;
}复杂度分析
- 时间复杂度：
O(mn)，其中m是nums1的长度，n是nums2的长度。 - 空间复杂度：
O(1)
4.3 解二：单调栈
当题目出现「找到最近一个比其大的元素」的字眼时，应该要会想到「单调栈」。
解释一下什么是单调栈：就是栈中存放的数据是有序的，比如：单调递增栈 和 单调递减栈
思路：
- 创建一个
map（哈希表），它的key为nums2中的值，value为key值右侧的 下一个更大元素 - 维护一个
stack单调栈，倒序遍历nums2数组 - 在循环中比较
nums2[i]与 单调栈中的值，将小于nums2[i]的值pop出，最后剩下的都是比nums2[i]大的数，且栈顶的值就是下一个更大元素 - 使用
map哈希表记录每个nums2[i]对应目标值。
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
const map = new Map<number, number>();
const stack = new ArrayStack<number>();
for (let i = nums2.length - 1; i >= 0; --i) {
const num = nums2[i];
while (stack.size() && num >= (stack.peek() as number)) {
stack.pop();
}
map.set(num, stack.size() ? (stack.peek() as number) : -1);
stack.push(num);
}
const res = new Array(nums1.length).fill(0).map((_, i) => map.get(nums1[i]) as number);
return res;
}复杂度分析
- 时间复杂度：
O(m + n)，其中m是nums1的长度，n是nums2的长度。 - 空间复杂度：
O(n)用于存储哈希表map
