今日文案:
梦魂拘检苦无方,悲喜于中不可藏。竟至泣啼如赤子,一生辛苦在初尝。
前言
太忙了最近,而且我开始跟不上了,哭泣,落下了好多天的学习记录,开始补了,加油加油!
一、滑动窗口最大值
题目描述:
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
题目来源:
解题思路:
1、暴力枚举:
循环移动的同时,每次遍历一遍数组,比较简单。
2、队列
在每个窗口中,插入所有元素,如果后面插入的比前面的大就全部弹出前面的,如果窗口移动移去的值==队列的头,去掉队列的头。
代码如下:
class Solution { public: deque<int> que; void push(int x) { while(!que.empty()&&x>que.back()) //插入 { que.pop_back(); } que.push_back(x); } void pop(int x) { if(!que.empty()&&que.front()==x) //比对看是否需要去掉 { que.pop_front(); } } int front() { return que.front(); } vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> ans; for(int i=0;i<k;i++) //确定窗口大小 { push(nums[i]); } ans.push_back(front()); for(int i=k;i<nums.size();i++) //滑动窗口 { pop(nums[i-k]); //移出窗口的值,传去与队列比较 push(nums[i]); //插入 ans.push_back(front()); //保留最大值 } return ans; } };
这是我个人的学习笔记,写得很粗略,只能用来辅助我自己理解。
二、前 K 个高频元素(未解决)
总结
二叉树我来了!