【每日算法】LeetCode239. 滑动窗口最大值

LeetCode 239. 滑动窗口最大值

对前端开发者而言，学习算法绝非为了"炫技"。它是你从"页面构建者"迈向"复杂系统设计者"的关键阶梯。它将你的编码能力从"实现功能"提升到"设计优雅、高效解决方案"的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

1. 题目描述

1.1 问题概要

给定一个整数数组nums和一个整数k，有一个大小为k的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的k个数字，滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

1.2 示例说明

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

2. 问题分析

2.1 核心挑战

这个问题看似简单，实则暗藏玄机：

• 暴力解法直观但效率低下（O(n×k)）
• 前端视角：想象你需要监控一个随时间变化的性能指标数据集，实时显示最近k个时间点的最大值
• 关键难点：如何在窗口滑动时，高效地维护当前窗口的最大值信息，而不是每次都重新计算

2.2 前端场景联想

考虑以下前端应用场景：

1. 性能监控面板：展示最近60秒内的最大FPS值
2. 实时数据仪表盘：显示最近100条请求的最大响应时间
3. 股票价格图表：实时计算最近N分钟的最高价
4. 视差滚动效果：根据最近N个滚动位置计算动画参数

3. 解题思路

3.1 暴力解法（基础思路）

遍历每个滑动窗口，在每个窗口内找到最大值。

时间复杂度: O(n×k)
空间复杂度: O(1) 或 O(n-k+1) 用于存储结果
评价: 简单直观，但效率低下，不适用于大规模数据

3.2 双端队列法（最优解）

维护一个单调递减的双端队列，存储元素的索引而非值：

3.2.1 核心原理

• 队列头部始终是当前窗口的最大值索引
• 队列中的元素按照从大到小的顺序排列（对应值）
• 当窗口滑动时：
  1. 移除队列中不在窗口范围内的索引
  2. 移除队列尾部所有小于新元素的索引（保持单调性）
  3. 将新元素索引加入队列尾部

3.2.2 算法复杂度

• 时间复杂度: O(n) - 每个元素最多进出队列一次
• 空间复杂度: O(k) - 双端队列最多存储k个元素
• 最优性: 这是理论上的最优时间复杂度

3.3 分块预处理法（备选思路）

将数组分成大小为k的块，预处理每个块的前缀最大值和后缀最大值。

时间复杂度: O(n)
空间复杂度: O(n)
优点: 实现相对简单，适合理解分治思想

4. 代码实现

4.1 暴力解法实现

/** * 暴力解法 - 直观但低效 * 时间复杂度: O(n×k) * 空间复杂度: O(n-k+1) */functionmaxSlidingWindowBruteForce(nums,k){if(!nums.length||k===0)return[];constresult=[];constn=nums.length;for(leti=0;i<=n-k;i++){letmax=-Infinity;for(letj=i;j<i+k;j++){max=Math.max(max,nums[j]);}result.push(max);}returnresult;}

4.2 双端队列法实现（最优解）

/** * 双端队列法 - 最优解 * 时间复杂度: O(n) * 空间复杂度: O(k) */functionmaxSlidingWindowDeque(nums,k){if(!nums.length||k===0)return[];constresult=[];constdeque=[];// 存储索引的单调递减队列for(leti=0;i<nums.length;i++){// 1. 移除队列中不在窗口范围内的索引while(deque.length>0&&deque[0]<=i-k){deque.shift();}// 2. 移除队列尾部所有小于当前元素的索引// 保持队列单调递减（对应值）while(deque.length>0&&nums[deque[deque.length-1]]<nums[i]){deque.pop();}// 3. 将当前索引加入队列deque.push(i);// 4. 当窗口形成时，将队列头部（最大值）加入结果if(i>=k-1){result.push(nums[deque[0]]);}}returnresult;}// 优化版本：使用双指针减少数组操作functionmaxSlidingWindowOptimized(nums,k){if(!nums.length||k===0)return[];constresult=[];constdeque=newArray(k);// 预分配数组空间letfront=0,rear=0;// 双指针模拟双端队列for(leti=0;i<nums.length;i++){// 移除不在窗口内的元素while(front<rear&&deque[front]<=i-k){front++;}// 维护单调递减性while(front<rear&&nums[deque[rear-1]]<nums[i]){rear--;}// 添加当前索引deque[rear++]=i;// 收集结果if(i>=k-1){result.push(nums[deque[front]]);}}returnresult;}

4.3 分块预处理法实现

/** * 分块预处理法 * 时间复杂度: O(n) * 空间复杂度: O(n) */functionmaxSlidingWindowBlock(nums,k){if(!nums.length||k===0)return[];constn=nums.length;constprefixMax=newArray(n);constsuffixMax=newArray(n);constresult=newArray(n-k+1);// 计算前缀最大值for(leti=0;i<n;i++){if(i%k===0){prefixMax[i]=nums[i];}else{prefixMax[i]=Math.max(prefixMax[i-1],nums[i]);}}// 计算后缀最大值for(leti=n-1;i>=0;i--){if(i===n-1||(i+1)%k===0){suffixMax[i]=nums[i];}else{suffixMax[i]=Math.max(suffixMax[i+1],nums[i]);}}// 计算每个窗口的最大值for(leti=0;i<=n-k;i++){constj=i+k-1;result[i]=Math.max(suffixMax[i],prefixMax[j]);}returnresult;}

5. 复杂度与优缺点对比

5.1 详细对比表格

5.2 性能实测对比（模拟数据）

// 测试不同数据规模下的性能consttestCases=[{n:1000,k:10,desc:'小数据量'},{n:100000,k:100,desc:'中等数据量'},{n:1000000,k:1000,desc:'大数据量'}];// 预期结果：// 1. 小数据量：三种方法都可接受// 2. 中等数据量：暴力法开始吃力// 3. 大数据量：只有双端队列法高效

6. 总结与前端应用

6.1 算法精髓总结

1. 单调队列的威力：双端队列法展示了如何通过数据结构设计将O(n×k)优化到O(n)
2. 空间换时间思想：分块法通过预计算加速查询
3. 前端工程师的启示：好的算法设计能显著提升用户体验，特别是在处理实时数据时

6.2 前端实际应用场景

6.2.1 性能监控系统

// 实时监控最近N个帧率的最高值classPerformanceMonitor{constructor(windowSize){this.windowSize=windowSize;this.fpsQueue=[];// 双端队列存储时间戳this.maxFPS=0;}recordFrame(timestamp){// 移除旧帧while(this.fpsQueue.length>0&&timestamp-this.fpsQueue[0]>this.windowSize){this.fpsQueue.shift();}// 添加新帧this.fpsQueue.push(timestamp);// 计算当前FPSconstcurrentFPS=this.fpsQueue.length/(this.windowSize/1000);this.maxFPS=Math.max(this.maxFPS,currentFPS);return{current:currentFPS,max:this.maxFPS};}}

6.2.2 无限滚动列表优化

// 虚拟滚动中计算可见区域的最大元素高度classVirtualScrollOptimizer{constructor(containerHeight,itemHeights){this.itemHeights=itemHeights;this.containerHeight=containerHeight;}// 使用滑动窗口计算渲染区域calculateRenderRange(scrollTop){// 确定可见区域conststartIdx=Math.floor(scrollTop/100);constendIdx=Math.min(startIdx+Math.ceil(this.containerHeight/100)+5,this.itemHeights.length);// 使用滑动窗口最大值算法优化渲染constmaxHeightInViewport=this.getMaxHeightInRange(startIdx,endIdx);return{startIdx,endIdx,maxHeight:maxHeightInViewport,buffer:5// 预渲染的缓冲项};}}

6.2.3 实时图表数据流

// 股票价格实时图表 - 计算最近N分钟最高价classStockChart{constructor(timeWindow){this.timeWindow=timeWindow;// 时间窗口（分钟）this.priceQueue=[];// {timestamp, price}this.maxPriceDeque=[];// 单调递减队列}addPrice(price,timestamp){// 清理过期数据while(this.priceQueue.length>0&&timestamp-this.priceQueue[0].timestamp>this.timeWindow*60000){this.priceQueue.shift();}// 更新价格队列this.priceQueue.push({price,timestamp});// 更新单调队列while(this.maxPriceDeque.length>0&&this.maxPriceDeque[this.maxPriceDeque.length-1].price<price){this.maxPriceDeque.pop();}this.maxPriceDeque.push({price,timestamp});// 清理单调队列中的过期数据while(this.maxPriceDeque.length>0&&timestamp-this.maxPriceDeque[0].timestamp>this.timeWindow*60000){this.maxPriceDeque.shift();}return{currentPrice:price,maxInWindow:this.maxPriceDeque[0].price,prices:this.priceQueue.map(p=>p.price)};}}