殡仪馆做网站的好处,合肥租房网,网站建设服装在线商城实训报告,做信息网站能挣钱吗day13 2023.12.11 代码随想录 今天刚出差回来#xff0c;拉下了很多天的博客#xff0c;慢慢补吧#xff0c;每天做当天的任务#xff0c;再补一篇博客。
1. 239滑动窗口最大值 本题就是每次窗口内容放在一个单调队列中#xff0c;那么每次直接返回队头元素#xff08;最…day13 2023.12.11 代码随想录 今天刚出差回来拉下了很多天的博客慢慢补吧每天做当天的任务再补一篇博客。
1. 239滑动窗口最大值 本题就是每次窗口内容放在一个单调队列中那么每次直接返回队头元素最大值即可在删一个元素以及填一个元素。所以关键就是这个单调队列怎么创建以及每次滑动该队列元素怎么变化。 首先就是创建单调队列实际我们要维护的单调队列内容并不包括所有窗口的元素例如{2, 3, 5, 1 ,4}单调队列里只维护{5, 4} 。保持单调队列里单调递减此时队列出口元素就是窗口里最大元素。创建该队列要求是每次增加元素要小于队尾元素即满足单调。如果大于队尾元素将队尾元素弹出。比如。先增加2再增加3时要增加的3队尾元素2因此弹出2增加3。增加5同理增加1时1小于队尾元素5正常添加。。。如此往下 单调队列创建后就要随窗口滑动不断更新如果滑动窗口要弹出的值队头元素即为最大值则需要改变单调队列。弹出队头元素即可。如果不等于则表示这次窗口滑动删掉的元素不影响新的单调队列因此单调队列不用改变这是滑动删除的元素。滑动也会增加一个元素增加元素后要保证队列仍是单调队列。同创建队列的要求。 每次窗口滑动满足上述要求则每次滑动只需要返回队头元素即可添加到一个结果数组即可。
class Solution {
private:class MyQueue{public:dequeint que;void pop(int value){//每次将窗口删除的元素传给队列,等于队头则弹出队头if(!que.empty() value que.front()){que.pop_front();}}void push(int value){while(!que.empty() valueque.back()){que.pop_back();}que.push_back(value);}int front(){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.front());for(int ik;inums.size();i){que.pop(nums[i-k]);que.push(nums[i]);result.push_back(que.front());}return result;}
};2. 347前K个高频元素 今天两道题难度都挺高的。所以都是直接看文字解释的。首先统计每个元素出现的频率想到的就是map。再根据map的value也就是频率构建小根堆。这些概念很熟悉但却没写过相应的代码因此这次理解起来还可以但对于代码不是很熟悉。慢慢来吧。保证小根堆大小为k每次删除头最小频率则遍历完后最后的小根堆就是要的k个频率最大的值。
class Solution {
public:// 小顶堆class mycomparison {public:bool operator()(const pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second;}};vectorint topKFrequent(vectorint nums, int k) {// 要统计元素出现频率unordered_mapint, int map; // mapnums[i],对应出现的次数for (int i 0; i nums.size(); i) {map[nums[i]];}// 对频率排序// 定义一个小顶堆大小为kpriority_queuepairint, int, vectorpairint, int, mycomparison pri_que;// 用固定大小为k的小顶堆扫面所有频率的数值for (unordered_mapint, int::iterator it map.begin(); it ! map.end(); it) {pri_que.push(*it);if (pri_que.size() k) { // 如果堆的大小大于了K则队列弹出保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素因为小顶堆先弹出的是最小的所以倒序来输出到数组vectorint result(k);for (int i k - 1; i 0; i--) {result[i] pri_que.top().first;pri_que.pop();}return result;}
};
