今天学习了队列的常见题型：
- 滑动窗口最大值，先进先出不难想到队列，最大值可以考虑优先队列，但是此题还是典型的单调队列（需要自己实现）
- 前k个高频元素，维护最大值常用优先队列，注意选的最小堆
7. 239滑动窗口最大值（队列）
题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
输入：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
每次动一下，前出一个，后进一个，可以想到队列。所以重点就是如何求窗口内的最大值。
a. 法一：优先队列
最大值，可以想到优先队列（堆），其中的大根堆可以实时维护一系列元素中的最大值。
对于本题而言，初始时，将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动窗口时，就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums中的位置出现在滑动窗口左边界的左侧。因此，当后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，可以将其永久地从优先队列中移除。
不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，可以在优先队列中存储二元组 (num,index)，表示元素num在数组中的下标为 index。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
// 先一口气放k个
priority_queue<pair<int, int>> q;
for (int i = 0; i < k; ++i) {
q.emplace(nums[i], i);
}
vector<int> ans = {q.top().first};
// 之后循环，每次放入一个，弹出最顶端的即可
for (int i = k; i < n; ++i) {
q.emplace(nums[i], i);
while (q.top().second <= i - k) {
q.pop();
}
ans.push_back(q.top().first);
}
return ans;
}
b.单调队列
这是单调队列的经典题目。
（1）需要一个什么样的队列
需要的队列是这样的：每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.front()就返回我们要的最大值。队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。
对于上图中窗口里的元素{2, 3, 5, 1 ,4}，单调队列里只维护{5, 4} 就够了，保持单调队列里单调递减，此时队列出口元素就是窗口里最大元素。
（2）队列如何配合滑动？
这只是最开始的窗口，此单调队列里维护着{5, 4} 怎么配合窗口进行滑动呢？
设计单调队列的时候，pop，和push操作要保持如下规则：
- pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
- push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则，每次窗口移动的时候，只要que.front()就可以返回当前窗口的最大值。
为了更直观的感受到单调队列的工作过程，以题目示例为例，输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3，动画如下：
（3）使用什么数据结构来实现这个队列
使用双端队列dequeue。
-
构造函数
deque<T>：默认构造一个空的双端队列。deque<T> d(n, value)：构造一个包含n个value值的双端队列。
-
元素访问
operator[]：随机访问，返回指定位置的元素，例如d[i]。at(index)：返回指定位置的元素并进行边界检查。front()：返回队列第一个元素的引用。back()：返回队列最后一个元素的引用。
-
修改操作
push_back(value)：在双端队列的末尾添加一个元素。push_front(value)：在双端队列的开头添加一个元素。pop_back()：删除并返回双端队列末尾的元素。pop_front()：删除并返回双端队列开头的元素。insert(position, value)：在指定位置插入一个元素。emplace_back(args...)：在末尾直接构造一个元素，避免额外的拷贝或移动操作。emplace_front(args...)：在开头直接构造一个元素。emplace(position, args...)：在指定位置直接构造一个元素。高效的插入方式。erase(position)：删除指定位置的元素。erase(begin, end)：删除指定范围[begin, end)内的元素。clear()：清空整个双端队列。resize(new_size)：调整双端队列的大小。
-
容量操作
size()：返回双端队列中元素的个数。empty()：判断双端队列是否为空。
-
迭代器操作
begin()：返回指向第一个元素的迭代器。end()：返回指向最后一个元素之后的迭代器。
-
赋值操作
assign(n, value)：将双端队列的内容替换为n个value值。assign(begin, end)：用迭代器范围[begin, end)替换双端队列的内容。
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;
}
};
（4）时空复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(k)
直观感受，在队列中 push元素的过程中，还有pop操作，不是纯粹的O(n)。其实nums 中的每个元素最多也就被 push_back 和 pop_back 各一次，没有任何多余操作，所以整体的复杂度还是 O(n)。
8. 347前 K 个高频元素
题目：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
- 输入:
nums = [1,1,1,2,2,3], k = 2 - 输出:
[1,2]
此题的解决思路有以下几步：
-
统计频率
使用哈希表map来统计：
unordered_map<int, int> map; // map<nums[i],对应出现的次数> for (int i = 0; i < nums.size(); i++) { map[nums[i]]++; } -
按照频率排序
解法一：使用快排把所有数字统计。但是需要将map转换为vector的结构，然后对整个数组进行排序
// 比较函数，用于排序 bool compare(const std::pair<int, int> &a, const std::pair<int, int> &b) { return a.second > b.second; // 频率高的排在前面 } // 将频率和数字存储在一个 vector 中 std::vector<std::pair<int, int>> freqVec(freqMap.begin(), freqMap.end()); // 按照频率排序 std::sort(freqVec.begin(), freqVec.end(), compare);解法二：这种场景下，其实只需要维护k个有序的序列就可以了，所以使用优先级队列是最优的。用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
-
取出频率最大的k个元素
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]]++;
}
// 对频率排序
// 定义一个小顶堆，大小为k
priority_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，则队列弹出，保证堆的大小一直为k
pri_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;
}
};
使用
unorder_map的场景和语法对于全体排序使用快排，维护一部分最大值和最小值常常考虑优先队列priority_queue
priority_queue<pair<int,int>,vector<pair<int,int>>,mycomp>pri_pue使用最大和最小堆中的哪一个，这个是典型题
小顶堆倒叙输出，其实只需要正常pop，但是倒着放到result里。
- 时间复杂度: O(nlogk)
- 空间复杂度: O(n)
今日古诗
鹧鸪天·送人
辛弃疾〔宋代〕
唱彻《阳关》泪未干，功名馀事且加餐。浮天水送无穷树，带雨云埋一半山。
今古恨，几千般，只应离合是悲欢？江头未是风波恶，别有人间行路难！