学校网站建设分工,湘西网站制作,广告设计模板免费,网站结构有哪些239. 滑动窗口最大值
题目链接#xff1a;239. 滑动窗口最大值
给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。 文章讲解…239. 滑动窗口最大值
题目链接239. 滑动窗口最大值
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。 文章讲解/视频讲解https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html 思路
设置一个大小为k的队列queue。
在滑动窗口处于初始位置时将初始的k个元素推入队列中 如果队列为空或者当前元素小于队列的队尾元素直接将nums[i]推入队列尾部 如果当前元素大于队列的队尾元素则循环判断只要队列的队尾元素小于当前元素就将当前队尾排出直到循环判断结束将nums[i]推入队列尾部。 此时队列的队首就是当前窗口的最大值。
滑动窗口开始移动时开始对整数数组nums的后续元素进行遍历 此时滑动窗口的范围为[i, i k - 1]如果nums[i - 1]等于队首元素则将队首排出说明此时队首已经不在滑动窗口中了 对于当前值nums[i]如果队列为空或nums[i]小于队列的队尾元素直接将nums[i]推入队列尾部如果此时队列大小大于k将队首排出 如果nums[i]大于队列的队尾元素则开始循环判断只要队列的队尾元素小于nums[i]就将当前队尾排出直到循环判断结束将nums[i]推入队列尾部。 同样的每次遍历当前队列的队首就是当前窗口的最大值。
上述方法在构建队列时可以保证队列中的元素是单调非增的因此队首就是当前窗口的最大值。同时因为需要对队列的队尾做排出操作用deque双向队列来作为队列的容器。 注如果用vector作为容器会超时。因为排出队首元素是o(n)复杂度的。
C实现
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {vectorint results;dequeint dQ;for(int i 0;ik;i){if(dQ.empty() || nums[i] dQ.back()){dQ.push_back(nums[i]);}else{while(!dQ.empty() dQ.back() nums[i]) dQ.pop_back();dQ.push_back(nums[i]);}}results.push_back(dQ.front());for(int i k;inums.size();i){if(nums[i - k] dQ.front()) dQ.pop_front();if(dQ.empty() || nums[i] dQ.back()){dQ.push_back(nums[i]);if(dQ.size() k) dQ.pop_front();}else{while(!dQ.empty() dQ.back() nums[i]) dQ.pop_back();dQ.push_back(nums[i]);}results.push_back(dQ.front());}return results;}
};347.前 K 个高频元素
题目链接347.前 K 个高频元素
给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 文章讲解/视频讲解https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html 思路
用小顶堆来实现。 定义一种node结构属性分别为值和频率。 首先遍历数组统计每个元素的出现频率将代表每个元素的node存入数组frequents。 定义一个存储node类型的小顶堆堆的判断标准是node之间的频率频率越低越靠前。 遍历数组frequents将元素不断地push进这个小顶堆中如果小顶堆的大小大于k则将小顶堆的堆顶排出。
最终小顶堆中的所有元素构成了前K个高频元素。
C实现
struct node{int value;int frequence;
};class Solution {
public:vectorint topKFrequent(vectorint nums, int k) {auto cmp [](node a, node b){return a.frequence b.frequence;};priority_queuenode, vectornode, decltype(cmp) Q(cmp);vectornode frequents;unordered_mapint, int hashMap;for(int i 0;inums.size();i){hashMap[nums[i]] 1;}for(auto p : hashMap){frequents.push_back({p.first, p.second});}for(int i 0;ifrequents.size();i){Q.push(frequents[i]);if(Q.size() k) Q.pop();}vectorint results;while(!Q.empty()){results.push_back(Q.top().value);Q.pop();}return results;}
};
