今日学习
滑动窗口最大值
题目链接/文章讲解/视频讲解：https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
第一想法
蛮有难度的一题，要先新建一个单调queue并满足enqueue和dequeue操作，下文代码含注释
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
// 定义一个名为 MonoQueue 的类，用于实现单调队列功能
class MonoQueue {
queue; // 单调队列数组
constructor() {
this.queue = []; // 初始化为空数组
}
// 入队操作，维护单调递减队列
enqueue(value) {
let back = this.queue[this.queue.length - 1]; // 获取队列最后一个元素
while (back !== undefined && back < value) { // 如果队列不为空且最后一个元素小于当前值
this.queue.pop(); // 不断弹出队尾元素，直到队列为空或队尾元素大于等于当前值
back = this.queue[this.queue.length - 1];
}
this.queue.push(value); // 将当前值入队
}
// 出队操作，如果出队元素等于参数值，则出队
dequeue(value) {
let front = this.front(); // 获取队首元素
if (front === value) { // 如果队首元素等于参数值
this.queue.shift(); // 出队
}
}
// 返回队首元素
front() {
return this.queue[0];
}
}
let helperQueue = new MonoQueue(); // 创建一个 MonoQueue 实例作为辅助队列
let i = 0, j = 0; // 初始化指针 i 和 j
let resArr = []; // 用于存储结果的数组
// 初始阶段，将滑动窗口内的元素加入辅助队列中
while (j < k) {
helperQueue.enqueue(nums[j++]);
}
resArr.push(helperQueue.front()); // 将第一个滑动窗口的最大值存入结果数组
// 滑动窗口移动阶段，更新最大值并存入结果数组
while (j < nums.length) {
helperQueue.enqueue(nums[j]); // 将新元素加入辅助队列
helperQueue.dequeue(nums[i]); // 尝试将窗口最左侧元素从队列中移出，若i没跟上，就代表在enqueue时已经pop出来了
resArr.push(helperQueue.front()); // 将当前窗口的最大值存入结果数组
i++, j++; // 移动窗口
}
return resArr; // 返回结果数组
};
前 K 个高频元素
题目链接/文章讲解/视频讲解：https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
第一想法
js中没有堆，得自行定义，我就先用最原始的方法，二刷再来解，代码有注释
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
const map = new Map()
for(n of nums){
map.set(n,map.has(n) ? map.get(n) + 1 : 1)
}
//将map转换为key-value键值对形式的数组，按照value降序进行排序
const list = Array.from(map).sort((a, b) => b[1] - a[1])
//取前k个元素，并只取其key
return list.slice(0,k).map(n => n[0])
};
总结
面试题：栈里面的元素在内存中是连续分布的么？
陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不一定是连续分布的。
陷阱2：缺省情况下，默认底层容器是deque，那么deque在内存中的数据分布是什么样的呢？
答案是：不连续的，下文也会提到deque。
用队列实现栈：
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了
括号匹配、字符串去重、逆波兰表达式
使用栈解决，匹配问题是栈的强项
通过求滑动窗口最大值，以及前K个高频元素介绍了两种队列：
单调队列和优先级队列，这是特殊场景解决问题的利器。
