网络异常，图片无法展示
|
概念
单调队列首先是一个单调序列，即序列中的元素是递增或者递减的。
如果这个序列是数组的子序列，且序列中的元素相对顺序与其在原数组中的相对顺序相同，那么就把这样的单调序列称为单调队列。
应用场景
维护数组区间中的最值。
举个栗子🌰：
有如下数组及一个长度为 k 的滑动窗口，滑动窗口会从数组最左侧移动到数组的最右侧，滑动窗口每次只向右移动一位，求滑动窗口最大值，以数组形式返回列表。
nums = [1,3,-1,-3,5,3,6,7], k = 3 复制代码
动画演示
网络异常，图片无法展示
|
主要操作
初始化
在 JavaScript 中，可以创建一个空数组，模拟单调队列。
插入元素
在队列末尾插入元素，插入之前需要将队列中违反单调性质的元素删除。
手写实现
// 实现单调递增队列类 class MonotonicQueue { // 初始化单调队列 constructor(){ this.queue = [] } // 插入操作 push(val){ // 插入之前，将队列中违反单调性质的元素删除 while(this.queue.length&&this.queue[this.queue.length-1]>=val) this.queue.pop(); this.queue.push(val) } } const instance = new MonotonicQueue(); instance.push(1); instance.push(3); instance.push(-1); instance.push(-3); instance.push(5); instance.push(3); instance.push(6); instance.push(7); console.log(instance.queue); // [-3,3,6,7] 复制代码
滑动窗口解题
// 给定数组 const nums = [1,3,-1,-3,5,3,6,7], // 窗口宽度 k = 3, // 初始化单调队列 queue = [], // 初始化结果数组 res = []; // 因为要获取窗口中的最大值，所以这里要维护的是单调递减队列，这样队首元素就维护了区间内的最大值 // 首先获取初始化窗口内元素的单调队列结果 for(let i = 0;i<k;i++){ // 将队列中违反单调性质的元素删除 while(queue.length&&queue[queue.length-1]<=nums[i]) queue.pop(); // 将当前元素下标插入单调队列 queue.push(i); } // 将窗口中的最大值插入到结果数组 res.push(nums[queue[0]]) // 遍历输入数组，模拟窗口滑动 for(let i = k;i<nums.length;i++){ // 如果队首元素超出了窗口范围，则删除 if(queue[0]<=i-k) queue.shift(); // 将队列中违反单调性质的元素删除 while(queue.length&&queue[queue.length-1]<=nums[i]) queue.pop(); // 将当前元素下标插入单调队列 queue.push(i); // 将窗口中的最大值插入到结果数组 res.push(nums[queue[0]]) } console.log(res); // [3,3,5,5,6,7] 复制代码
至此，我们就完成了单调队列的概念、应用场景及示例以及手写实现和示例问题求解的全过程。
如有任何问题或建议，欢迎留言讨论！
