中山的网站建设公司,创新的企业网站建设,pc访问手机网站跳转,转塘有做网站的吗题目#xff1a;
链接#xff1a;剑指 Offer 59 - I. 滑动窗口的最大值#xff1b;LeetCode 239. 滑动窗口最大值 难度#xff1a;困难 下一篇#xff1a;剑指 Offer 59 - II. 队列的最大值#xff08;单调队列#xff09;
给你一个整数数组 nums#xff0c;有一个大…题目
链接剑指 Offer 59 - I. 滑动窗口的最大值LeetCode 239. 滑动窗口最大值 难度困难 下一篇剑指 Offer 59 - II. 队列的最大值单调队列
给你一个整数数组 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 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 输入nums [1], k 1 输出[1] 提示
1 nums.length 105-104 nums[i] 1041 k nums.length
方法一
优先队列不推荐
优先队列的本质是最大堆可以帮助实时维护一个滑动窗口中的最大值。 初始时将数组nums前k个元素插入优先队列中。每当右移窗口时就将新的元素插入优先队列最大堆那么此时堆顶的元素就是最大值。然而这个最大值有可能经过右移已不在窗口中在窗口左边界的更左位置所以我们要根据这个栈顶元素的实际坐标移除已不在窗口中的堆顶元素直到堆顶元素确实在窗口范围中此时的堆顶元素才是窗口内的最大值。 为了方便判断堆顶元素与滑动窗口的位置关系我们可以在优先队列中存储二元组 (num,index)表示元素 num 在数组中的下标为 index。优先队列会默认按第一个整数进行优先级排序。
代码一
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {int n nums.size();if(n 0) return {};priority_queuepairint, int window; // 维护一个滑动窗口内的优先队列vectorint ans;for(int i 0; i k; i){window.emplace(nums[i], i);}ans.emplace_back(window.top().first);for(int i k; i n; i){window.emplace(nums[i], i);while(window.top().second i - k) { // 将滑动窗口外的元素删掉window.pop();}ans.emplace_back(window.top().first);}return ans;}
};时间复杂度O(NlogN)。在最坏情况下nums数组呈单调递增优先队列中插入了所有元素且没有元素被删除将一个元素插入优先队列的时间复杂度为O(logN)n个元素为O(NlogN)。 空间复杂度O(N)。在上述的最坏情况下优先队列需要n个元素的空间。
方法二
单调队列推荐
使用双端队列deque实现的单调队列详解看单调队列结构解决滑动窗口问题。 顺着方法一的思路进行优化方法一中优先队列在发现堆顶元素在窗口外之前仍保留窗口外元素的特点是冗余的。我们可以发现若滑动窗口中有两个下标 i jnums[i] nums[j]只要 i 还在窗口中j 一定也在窗口中nums[i] 就一定不是窗口最大值了所以 nums[i] 可以被永久移除。这符合单调队列的性质。
代码二
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {int n nums.size();if(n 0) return {};dequeint window; //单调递减队列vectorint ans;for(int i 0; i n; i){while(!window.empty() window.back() nums[i]) { //维护一个单调递减队列把单调队列中比新元素小的元素全部删除window.pop_back();}window.emplace_back(nums[i]);if(i k - 1) {ans.emplace_back(window.front());}else if(i k) {if(window.front() nums[i - k]) window.pop_front(); //维护一个单调递减队列删除滑动窗口右移丢失的最大值ans.emplace_back(window.front());}}return ans;}
};时间复杂度O(N)。 空间复杂度O(k)。窗口右移时从队首弹出元素保证了队列内不会有超过 k1 个元素。
