阿里巴巴申请网站怎么做,包装网站建设,新东方托福班价目表,永嘉网站制作系统239. 滑动窗口最大值 思路#xff1a; 用遍历区间的元素时#xff0c;维护一个单调队列#xff0c;从大到小排列。 要找到最大值#xff0c;实际单调队列保存区间内最大值及最大值右侧的第二大值#xff08;用于当前最大值处于区间左端#xff0c;在区间右移时更新临时最…
239. 滑动窗口最大值 思路 用遍历区间的元素时维护一个单调队列从大到小排列。 要找到最大值实际单调队列保存区间内最大值及最大值右侧的第二大值用于当前最大值处于区间左端在区间右移时更新临时最大值只需要用临时最大值和新区间右端元素比较就可以知道新的最大元素。为什么强调是最大值右侧的第二大值因为最大值左侧的元素必然在最大值前离开区间。 特殊情况 代码实现
class Solution {
private:class Myqueue{public:dequeint que;// 使用deque来实现单调队列// 每次弹出的时候比较当前要弹出的数值是否等于队列出口元素的数值如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop(int num){if(!que.empty() num que.front()){que.pop_front();}}// 如果push的数值大于入口元素的数值那么就将队列后端的数值弹出直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。void push(int num){while(!que.empty() num que.back()){que.pop_back();}que.push_back(num);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front(){return que.front();}};
public:vectorint maxSlidingWindow(vectorint nums, int k) {vectorint maxNum;Myqueue que;int temp 0;for(int left 0, right k-1; right nums.size(); left, right){//实际temp遍历nums每个元素且每个元素只遍历到一次while(temp right){que.push(nums[temp]);temp;}maxNum.push_back(que.front());que.pop(nums[left]);}return maxNum;}
};347.前 K 个高频元素 思路 用unordered_map 保存元素出现频率使用优先队列的小顶堆 最小的元素最优先出队(自定义数据结构重定义排序规则) 特殊情况 class Solution {
public://自定义数据结构重定义排序规则class mycmp{public:bool operator()(const pairint, int lfs, const pairint, int rfs){return lfs.second rfs.second;}};vectorint topKFrequent(vectorint nums, int k) {//用unordered_map 保存元素出现频率unordered_mapint,int Map;for(int num : nums){Map[num];}//使用优先队列的小顶堆 最小的元素最优先出队priority_queuepairint,int, vectorpairint, int, mycmp pri_que;for(auto p : Map){pri_que.push(p);if(pri_que.size()k) pri_que.pop();}vectorint result(k);for(int i result.size()-1; i 0; i--){result[i] pri_que.top().first;pri_que.pop();}return result;}
};
