网站富文本的内容怎么做,欧洲applestore,个人网站开发开题报告,it在线学习网站开发题目
给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1#xff1a;
输入#xff1a;nums [1,3,-1,-3,5,3,6,7], …题目
给你一个整数数组 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
滑动窗口
这道题和之前的滑动窗口的题目有点类似要避免直接两层循环暴力求解可以使用滑动窗口【LeetCode热题100】【滑动窗口】找到字符串中所有字母异位词_找到字符串中所有字母异位 题解-CSDN博客
要寻找这个滑动窗口的最大值最快的方法是使用一个大顶堆堆的插入元素的时间复杂度为logn这样不用遍历窗口的每个元素就可以找出最大值
但这样还有一个问题那就是滑动窗口移动的时候如果删除左边被移出窗口的元素堆删除指定元素并不简单解决的方法就是不删除当堆顶元素为已经移出窗口的元素时pop堆顶元素就行这样就可以避免找到的最大值是已经移除的元素
为了实现判断这个元素是否已经移除窗口我们采用二元组来存储每个元素本身和它的索引当索引小于等于当前的i-k说明这个元素已经不在了做掉
还有一点就是C没有堆这个容器但是有优先队列这个是堆实现的可以当成堆来用而且默认是大顶堆而C中的二元组pari比较大小的时候默认是先比较第一个所以我们需要把元素本身放第一个
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {vectorintanswer;priority_queuepairint,intdeap;for(int i0;ik;i)deap.emplace(nums[i],i);answer.push_back(deap.top().first);for(int ik;inums.size();i){deap.emplace(nums[i],i);while(deap.top().secondi-k){deap.pop();}answer.push_back(deap.top().first);}return answer;}
};
