今日刷题重点—队列
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]
解释：
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1 输出：[1]
示例 3：
输入：nums = [1,-1], k = 1 输出：[1,-1]
示例 4：
输入：nums = [9,11], k = 2 输出：[11]
示例 5：
输入：nums = [4,-2], k = 2 输出：[4]
思路分析(明日完善)
单调队列的使用
这道题不复杂，难点在于如何在 O(1) 时间算出每个「窗口」中的最大值，使得整个算法在线性时间完成。就需要「单调队列」这种特殊的数据结构来辅助了。
C++普通队列:
class Queue { void push(int n); // 或 enqueue，在队尾加入元素 n void pop(); // 或 dequeue，删除队头元素 }
单调队列:
class MonotonicQueue { // 在队尾添加元素 n void push(int n); // 返回当前队列中的最大值 int max(); // 队头元素如果是 n，删除它 void pop(int n); }
实现单调队列数据结构
单调队列的 push 方法依然在队尾添加元素，但是要把前面比新元素小的元素都删掉; 要用到双端队列:deque
class MonotonicQueue { private: deque<int> data; public: void push(int n) { while (!data.empty() && data.back() < n) data.pop_back(); data.push_back(n); } };
加入数字的大小代表人的体重，把前面体重不足的都压扁了，直到遇到更大的量级才停住。
如果每个元素被加入时都这样操作，最终单调队列中的元素大小就会保持一个单调递减的顺序，因此我们的 max() API 可以可以这样写：
int max() { return data.front(); }
pop() API 在队头删除元素 n，也很好写：
void pop(int n) { if (!data.empty() && data.front() == n) data.pop_front(); }
之所以要判断 data.front() == n 是因为我们想删除的队头元素 n 可能已经被「压扁」了，这时候就不用删除了：
至此，单调队列设计完毕.
图解:
参考代码
class MonotonicQueue { private: deque<int> Q; public: void push(int n) { while(!Q.empty() && Q.back() < n) { //把 < n的元素都压扁 Q.pop_back();//从后面弹出.. } Q.push_back(n); } int max() { return Q.front();//最大的便是对头元素 } void pop(int n) { if(!Q.empty()&& Q.front()==n) { //如果窗口移除的元素= 最大值, 则单调队列中删除该元素. Q.pop_front();//从前面弹出. } } }; //单调队列的使用 vector<int> maxSlidingWindow(vector<int>& nums, int k) { MonotonicQueue window; vector<int> res; for(int i = 0;i < nums.size();i++){ if(i < k-1){//先填满窗口的k-1 window.push(nums[i]); }else{//窗口向前移动 window.push(nums[i]); // 窗口变成k-1 ==>右边界右移动 res.push_back(window.max()); //弹出最大的元素 window.pop(num[i-k+1]);//删除最左边的元素.==> 左边界右移动 } } return res; }
复杂度分析
时间复杂度:O ( N ) : 因为每个元素只被push和pop了一次.
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
思路分析
这个题考察内容:
- 要统计元素出现频率==>使用map
- 对频率排序=>使用优先队列
- 找出前K个高频元素
priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
什么是堆呢?
堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。
如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
所以我们可以用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。(当然如果是大根堆,那么弹出前k个元素就行.)
参考代码
//定义优先队列的排序规则(优先队列和常规的排序规则(如快排)正好相反 class mycomparison { public: bool operator(const pair<int,int>& l,const pair<int,int>& r) { return l.second > r.second; } }; class Solution { public: //小顶堆 vector<int> topKFrequent(vector<int>& nums, int k) { //要统计元素出现的频率 unordered_map<int,int> map; for(int i = 0;i < nums.size();i++){ map[nums[i]]++; } //对频率排序 //定义一个小根堆,大小为k priority_queue<pair<int,int>,vector<pair<int,int>>, mycomparison> Q; //用固定大小为k的小根堆,扫到所有频率的数值 for(unordered_map<int,int>::iterator it = map.begin(); it!= map.end(); it++){ Q.push(*it); if(Q.size()>k){ Q.pop(); } } //找出前k个高频元素,因为小根堆先弹出的是最小的. vector<int> res(k); for(int i = k-1; i>=0;i--){ res[i] = Q.top().first; Q.pop(); } return res; } };
注:pair可看做map的一个子元素模板,可以对map进行赋值,初始化等操作.
本文相关内容参考自卡尔大佬的代码随想录 和 LeetCode一位大佬的思路
