LeetCode 239. 滑动窗口最大值 | C 优先队列与单调队列双解法题解 题目描述题目级别困难 (Hard)给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例 1输入nums [1,3,-1,-3,5,3,6,7], k 3输出[3,3,5,5,6,7] 解题思路与代码实现这道题是滑动窗口系列中的困难题核心痛点在于窗口每次向右滑动时如何快速剔除离开窗口的旧元素并获取当前窗口内的新最大值我们提供两种解法一种是思维直观的“优先队列大顶堆法”另一种是面试官最期望看到的极致O ( N ) O(N)O(N)性能的“单调队列法”。 解法一优先队列 延迟删除 (大顶堆)最直观的想法是用一个大顶堆priority_queue来维护窗口内的最大值。但是优先队列不支持直接删除底层的非堆顶元素。“延迟删除”技巧我们将数组的(数值, 索引)作为一个pair存入大顶堆。窗口滑动时无脑将新元素压入堆中。如果此时堆顶的最大元素实际上已经“过期”即它的索引≤ i − k \le i - k≤i−k滑出了当前窗口我们就把这个堆顶元素弹出去直到堆顶元素合法为止。 C 代码实现classSolution{public:vectorintmaxSlidingWindow(vectorintnums,intk){// priority_queue 默认是大顶堆存储 pair数值, 索引priority_queuepairint,intpq;vectorintres;// 1. 先将前 k 个元素入堆初始化第一个窗口for(inti0;ik;i){pq.emplace(nums[i],i);}res.push_back(pq.top().first);// 2. 窗口开始向右滑动for(intik;inums.size();i){// 将新进入窗口的元素加入堆中pq.emplace(nums[i],i);// 核心延迟删除。如果堆顶元素的索引已经不在窗口内了就把它弹出去while(pq.top().secondi-k){pq.pop();}// 此时的堆顶元素一定是当前窗口内的合法最大值res.push_back(pq.top().first);}returnres;}}; 解法二单调队列 (面试终极最优解)优先队列法的时间复杂度是O ( N log ⁡ N ) O(N \log N)O(NlogN)。为了将时间复杂度极致压缩到O ( N ) O(N)O(N)我们需要使用一个双端队列deque来维护一个严格单调递减的索引队列。核心思想队首踢老队尾踢小队尾维护单调性新元素准备入队时如果它比队尾的元素大那么队尾的元素就变成了“既小又老”的废物在未来的窗口中绝不可能是最大值直接把队尾弹出。队首清理过期元素如果队首元素的索引已经离开了窗口范围就将队首弹出。经过这两步过滤队首元素永远是当前窗口内最大值的索引。 进阶 C 代码实现classSolution{public:vectorintmaxSlidingWindow(vectorintnums,intk){vectorintres;dequeintdq;// 双端队列存储的是元素的【索引】for(inti0;inums.size();i){// 1. 队首清理踢老如果队首的索引已经滑出了窗口将其弹出if(!dq.empty()dq.front()i-k){dq.pop_front();}// 2. 队尾清理踢小保持队列的单调递减性// 如果新来的数比队尾的数大说明队尾的数永远没有出头之日直接弹出while(!dq.empty()nums[dq.back()]nums[i]){dq.pop_back();}// 3. 将当前元素的索引加入队尾dq.push_back(i);// 4. 当窗口长度达到 k 时开始记录答案队首永远是最大值的索引if(ik-1){res.push_back(nums[dq.front()]);}}returnres;}};