单调队列+滑动窗口

对应力扣239滑动窗口的最大值给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。暴力解法设置左右指针形成固定长度 k的窗口左指针left右指针rightleftk-1遍历窗口内[left, right]的 k 个元素找到并记录最大值左右指针同时右移 1 位重复步骤 2直到窗口滑出数组末尾最终将所有窗口的最大值组成数组返回。时间复杂度为On×kn为数组长度k为窗口长度/** * param {number[]} nums * param {number} k * return {number[]} */ var maxSlidingWindow function(nums, k) { const res []; const n nums.length; let left 0; // 右指针最大为n-1窗口左边界最大为n-k while (left n - k) { let right left k - 1; let max nums[left]; // 遍历当前窗口找最大值你的核心思路 for (let i left; i right; i) { max Math.max(max, nums[i]); } res.push(max); left; // 指针右移窗口滑动 } return res; };为什么暴力法效率低重复计算是关键暴力法的致命问题是存在大量重复计算窗口每次只右移 1 位相邻两个窗口有 k-1 个元素是重叠的但暴力法会重新遍历全部 k 个元素找最大值浪费了重叠部分的计算结果单调队列双端队列 Deque要解决重复计算问题核心是用一个特殊队列记录「窗口内可能成为最大值的元素下标」让队列保持单调递减这样队列队首永远是当前窗口的最大值下标窗口滑动时只需维护这个队列无需遍历窗口。先理解单调递减队列的核心规则队列中存储的是nums 的元素下标而非值且满足下标对应的值从队首到队尾严格单调递减比如队列里的下标对应值是 [5,3,-1]而非 [3,5,-1]。队列的3 个核心维护操作窗口滑动时执行去尾当新元素进入窗口时若新元素值 ≥ 队尾下标对应的值则队尾出队因为该队尾元素在窗口内不可能成为后续任何窗口的最大值直接淘汰重复此操作直到队列单调递减入队将新元素的下标加入队尾此时队列仍保持单调递减删头若队首下标 ≤ 窗口左边界 - 1说明队首元素已滑出窗口则队首出队保证队首始终在窗口内。最优解核心步骤全程只需遍历数组 1 次初始化双端队列 deque存储下标、结果数组 res遍历数组 nums 的每个元素下标为i步骤 1去尾→ 维护队列单调递减淘汰比当前元素小的队尾步骤 2入队→ 将i加入 deque 队尾步骤 3删头→ 移除滑出窗口的队首下标步骤 4记录最大值→ 当i ≥ k-1说明第一个窗口已形成将nums[deque[0]]队首是窗口最大值下标加入 res遍历结束res 即为所有窗口的最大值数组。用数组模拟双端队列shift()删队首、pop()删队尾、push()入队尾/** * param {number[]} nums * param {number} k * return {number[]} */ var maxSlidingWindow function(nums, k) { const res []; const deque []; // 双端队列存储nums的下标保持单调递减 const n nums.length; for (let i 0; i n; i) { // 操作1去尾 - 维护单调递减淘汰比当前元素小的队尾 while (deque.length nums[i] nums[deque[deque.length - 1]]) { deque.pop(); } // 操作2入队 - 加入当前元素下标 deque.push(i); // 操作3删头 - 移除滑出窗口的队首窗口左边界为i-k1 while (deque[0] i - k) { deque.shift(); } // 操作4记录最大值 - 第一个窗口形成后ik-1队首即为当前窗口最大值 if (i k - 1) { res.push(nums[deque[0]]); } } return res; };为什么左边界是i-k1你问的这个问题是滑动窗口的核心边界计算规则i-k1是当前遍历下标i作为窗口右边界时窗口对应的左边界下标核心推导基于「窗口长度固定为k 数组下标从 0 开始」两个前提下面用大白话 数学推导 例子讲透保证一看就懂一、核心前提先记死所有推导的基础力扣 239 题是固定长度滑动窗口窗口内元素的个数严格等于k比如k3窗口永远包含 3 个元素数组 / 字符串的下标从 0 开始这是编程的通用规则也是边界计算的关键我们遍历数组的下标i始终作为当前窗口的「右边界」窗口的最后一个元素的下标。二、数学公式推导10 秒看懂最直观我们的目标是已知窗口右边界下标i 窗口长度k求窗口左边界下标left。第一步先想「连续数字的个数」计算规则对于任意连续的下标区间[left, i]left ≤ i区间内的元素个数计算公式是元素个数i−left1✅ 验证下标从 0 开始区间[0,2]2-013个元素0、1、2正确区间[1,3]3-113个元素1、2、3正确区间[2,4]4-213个元素2、3、4正确。第二步结合「窗口长度 k」推导左边界因为固定窗口的元素个数必须等于k所以代入公式得ki−left1将公式移项求解left小学一元一次方程lefti−k1这就是i-k1的数学由来没有任何复杂逻辑纯粹是「下标从 0 开始」的个数计算规则推导结果。