1、优先队列
优先队列在普通队列的基础上给每个元素增加了优先级,这样每次出队的元素不再是队首的元素,而是队列中优先级最高的元素,而具体的优先级可以自行定义,典型的就是按元素从大到小或从小到大的顺序定义优先级。
在STL中也提供了优先队列模板:priority_queue
2、单调队列
所谓单调队列就是一个单调递增或递减的队列,并不是什么神奇的东西。
单调队列(就递增来说)严格来说就是队头的原素是最大的,不断从队尾加原素,如果队尾的原素比要加入来的原素大,就不断退队,就到队尾的原素比要加入来的原素小或等于要加入来的原素。
3、区别:
单调队列与优先队列的区别:单调队列的长度取决于输入数据的合法性,而优先队列的长度始终与输入数据的数量等同。而他们的单调性都是单调递减或单调递增。
在单调队列的应用上,它经常用来解决定长连续子区间的最值问题:
239. 滑动窗口最大值
此时我们需要一个队列,这个队列呢,放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么。
那么我们需要的恰好是单调队列:
class MyQueue {
public:void pop(int value) {}void push(int value) {}int front() {return que.front();}
};
每次窗口移动的时候,调用que.pop(滑动窗口中移除元素的数值),que.push(滑动窗口添加元素的数值),然后que.front()就返回我们要的最大值。
我们需要自己实现这么个队列。
设计单调队列的时候,pop,和push操作要保持如下规则:
- pop(value):如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作
- push(value):如果push的元素value大于入口元素的数值,那么就将队列入口的元素弹出,直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则,每次窗口移动的时候,只要问que.front()就可以返回当前窗口的最大值。
那么我们用什么数据结构来呢?
使用deque实现这个单调队列最为合适,常用的queue在没有指定容器的情况下,deque就是默认底层容器。
基于刚刚说过的单调队列pop和push的规则,代码不难实现,如下:
class MyQueue { //单调队列(从大到小)
public:deque<int> que; // 使用deque来实现单调队列// 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}// 如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front() {return que.front();}
};
完整代码·
class Solution {
private:class MyQueue { //单调队列(从大到小)public:deque<int> que; // 使用deque来实现单调队列// 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}// 如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;for (int i = 0; i < k; i++) { // 先将前k的元素放进队列que.push(nums[i]);}result.push_back(que.front()); // result 记录前k的元素的最大值for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}
};
单调队列的时间复杂度是 O(n)。
空间复杂度因为我们定义一个辅助队列,所以是O(k)。
347.前 K 个高频元素
开始进入优先队列的应用
这道题目主要涉及到如下三块内容:
- 要统计元素出现频率
- 对频率排序
- 找出前K个高频元素
首先统计元素出现的频率,这一类的问题可以使用map来进行统计。
然后是对频率进行排序,这里我们可以使用一种 容器适配器就是优先级队列。
// 时间复杂度:O(nlogk)
// 空间复杂度:O(n)
class Solution {
public:// 小顶堆class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {// 要统计元素出现频率unordered_map<int, int> map; // map<nums[i],对应出现的次数>for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// 对频率排序// 定义一个小顶堆,大小为kpriority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小为k的小顶堆,扫面所有频率的数值for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // 如果堆的大小大于了K,则队列弹出,保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};
总结