网站信息备案查询,服务器租用收费标准,营销网建,深汕特别合作区招聘每日一题(LeetCode)----栈和队列–滑动窗口最大值
1.题目#xff08;239. 滑动窗口最大值#xff09; 给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 …每日一题(LeetCode)----栈和队列–滑动窗口最大值
1.题目239. 滑动窗口最大值 给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1 输入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 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例 2 输入nums [1], k 1
输出[1]提示 1 nums.length 105-104 nums[i] 1041 k nums.length
2.解题思路
思路一使用优先队列
优先队列的底层实现是堆,默认是大顶堆
1.我们先创建一个优先队列底层是大顶堆的便于我们维护最大值且这个优先队列中的每一个元素都是二元组的每一个二元组的元素的第一个表示的是数组中的一个数第二个表示的是这个数在数组中对应的下标便于我们之后将不在滑动窗口范围内的元素删除 然后再创建一个动态数组用来存每一个滑动窗口的最大值
2.初始时我们先根据k变量的大小把数组的前k个元素连带着它们的下标放入到优先队列中去
3.我们从第k1个元素开始向后遍历每遍历到一个元素将当前元素连带着它的下标作为一个二元组元素放入到优先队列中去然后将优先队列的首元素中存的下标与当前滑动窗口的左边界进行比较如果比左边界小那么就删除当前优先队列的首元素直到优先队列的首元素中存的下标比左边界大结束然后将当前优先队列首元素存的值放入到动态数组中去继续向后遍历
在滑动窗口中在这种情况下这个值在数组 nums\textit{nums}nums 中的位置出现在滑动窗口左边界的左侧。因此当我们后续继续向右移动窗口时这个值就永远不可能出现在滑动窗口中了我们可以将其永久地从优先队列中移除。
我们不断地移除堆顶的元素直到其确实出现在滑动窗口中。此时堆顶元素就是滑动窗口中的最大值。
思路来源:力扣官方题解
链接https://leetcode.cn/problems/sliding-window-maximum/
思路二双向队列单调队列
1.我们先创建一个双向队列单调队列这个队列存的是数组中元素的下标我们要保证这个队列中存的元素的下标对应的数是递减的然后我们再创建一个动态数组用来存每一个滑动窗口的最大值
2.初始时我们先根据k变量的大小先对数组中前k个元素进行处理当队列为空时我们直接把当前遍历到的元素对应的下标放入到队列末尾当队列不为空时且当前遍历到的元素的值大于队列末尾下标所对应的数的值那么我们删除队列的末尾元素继续与队列末尾元素进行比较直到当前遍历到的元素的值小于队列末尾下标所对应的数的值我们将当前元素对应的下标放入到队列的末尾
3.我们从第k1个元素开始向后遍历每遍历到一个元素看队列是否为空当队列为空时我们直接把当前遍历到的元素对应的下标放入到队列末尾当队列不为空时且当前遍历到的元素的值大于队列末尾下标所对应的数的值那么我们删除队列的末尾元素继续与队列末尾元素进行比较直到当前遍历到的元素的值小于队列末尾下标所对应的数的值我们将当前元素对应的下标放入到队列的末尾再将队列的首元素的值与当前滑动窗口的左边界进行比较如果比左边界小那么就删除当前队列的首元素直到队列的首元素的值比左边界大结束然后将当前队列首元素在数组中对应的值放入到动态数组中去继续向后遍历
思路来源:力扣官方题解
链接https://leetcode.cn/problems/sliding-window-maximum/
3.写出代码
思路一的代码
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {priority_queuepairint,int q;int nnums.size();for(int i0;ik;i){q.emplace(nums[i],i);}vectorint ans{q.top().first};for(int ik;in;i){q.emplace(nums[i],i);while(q.top().secondi-k){q.pop();}ans.push_back(q.top().first);}return ans;}
};思路来源:力扣官方题解
链接https://leetcode.cn/problems/sliding-window-maximum/
思路二的代码
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {dequeint q;int nnums.size();for(int i0;ik;i){while(!q.empty()nums[i]nums[q.back()]){q.pop_back();}q.push_back(i);}vectorint ans{nums[q.front()]};for(int ik;in;i){while(!q.empty()nums[i]nums[q.back()]){q.pop_back();}q.push_back(i);while(q.front()i-k){q.pop_front();}ans.push_back(nums[q.front()]);}return ans;}
};思路来源:力扣官方题解
链接https://leetcode.cn/problems/sliding-window-maximum/
