北京价格网站建设,wordpress 教学培训,seo外包 杭州,网页制作模板怎么制作题目1#xff1a;239 滑动窗口最大值
题目链接#xff1a;239 滑动窗口最大值
题意
长度为K的滑动窗口从整数数组的最左侧移动到最右侧#xff0c;每次只移动1位#xff0c;求滑动窗口中的最大值
不能使用优先级队列#xff0c;如果使用大顶堆#xff0c;最终要pop的…题目1239 滑动窗口最大值
题目链接239 滑动窗口最大值
题意
长度为K的滑动窗口从整数数组的最左侧移动到最右侧每次只移动1位求滑动窗口中的最大值
不能使用优先级队列如果使用大顶堆最终要pop的元素不知道是哪一个因为大顶堆已经对队列中的元素进行排序了元素的顺序发生了改变 暴力解法
对窗口内的所有元素进行排序 单调队列
由于窗口每次只移动1步所以每真正push一次就收集一次最大值即可最大值放到队列的出口
队列只维护窗口中的最大值即可且队列里的元素是从左到右依次递减的
pop()若滑动窗口原本要移除的元素(val)就是单调队列的出口(front)元素(滑动窗口的最大值)那么就弹出元素
push()如果要放入的元素(val)大于入口(back)的元素就将入口处(back)小于val的元素逐个卷走元素再在入口处(back)处入栈
getmaxvalue()每次移动窗口时队列出口处(front())的元素即为当前窗口的最大值 伪代码 逻辑
例1前一个滑动窗口删除的元素会不会影响后一个滑动窗口 代码
class Solution {
private:class MyQueue{public:dequeint que;//双向队列void pop(int val){if(!que.empty()que.front()val){que.pop_front();}}void push(int val){//去掉入口处比其小的元素while(!que.empty()que.back()val){que.pop_back();}que.push_back(val);}int getmaxvalue(){return que.front();}};
public:vectorint maxSlidingWindow(vectorint nums, int k) {MyQueue que;vectorint result;for(int i0;ik;i){que.push(nums[i]);}//第一个滑动窗口的元素result.push_back(que.getmaxvalue());for(int ik;inums.size();i){//先弹出元素因为窗口的大小是一定的只能先弹出元素再放入元素que.pop(nums[i-k]);//再放入元素que.push(nums[i]);//求最大值result.push_back(que.getmaxvalue());}return result;}
};
时间复杂度: O(n)空间复杂度: O(k)
题目2347 前K个高频元素
题目链接347 前K个高频元素
题意
返回整数数组nums中出现频率前k高的元素
暴力解法
使用map数组元素是key频率是value然后将value从大到小排序输出前k个元素所有元素进行排序 优先级队列(小顶堆)
为了优化时间复杂度可以只维护k个元素没有必要排序所有元素想到使用优先级队列。
大顶堆小顶堆擅长求解在大数据集内求排名靠前的元素堆的底层实现是二叉树
那么使用大顶堆还是使用小顶堆呢
如果使用大顶堆那么加入该元素时弹出最大值不符题意
如果使用小顶堆那么加入该元素时弹出最小值符合题意所以使用小顶堆
使用优先级队列实现大顶堆的话cmopare函数从大到小排实现小顶堆的话compare函数从小到大排 伪代码 代码
class Solution {
public:class mycomparision{public:bool operator()(const pairint,int kv1,const pairint,int kv2){return kv1.second kv2.second;}};//定义一个类之后一定要添加;vectorint topKFrequent(vectorint nums, int k) {unordered_mapint,int map;//统计元素出现的频率for(int i0;inums.size();i){map[nums[i]];}//使用优先级队列定义小顶堆priority_queuepairint,int,vectorpairint,int,mycomparision que;//pairint,int表示键值对的数据类型元素(int),频率(int)//vectorpairint,int表示vector作为que的底层容器存储元素//遍历map中的元素小顶堆只维护前k个高频元素for(unordered_mapint,int::iterator itmap.begin();it!map.end();it){que.push(*it);//*it代表迭代器it指向的key-value键值对if(que.size()k){que.pop();//弹出当前小顶堆中的最小值}}//将小顶堆中频率排名前k的key元素按照频率从高到低放到数组中vectorint result(k);//这里一定要定义result的大小因为后续是对result的下标位置进行操作for(int ik-1;i0;i--){result[i] que.top().first;que.pop();}return result;}
};
时间复杂度: O(nlogk)空间复杂度: O(n)
逻辑
例1最后将堆中的元素放入到数组中时如果写出这样
vectorint result;
会报如下错误 原因就是还未给result数组分配内存空间所以访问result[i]时出错相当于访问了一个空的空间和访问空指针差不多一个意思。
