https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html#%E6%80%9D%E8%B7%AF
给你一个整数数组 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]
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
只想到了暴力解法,n*k的复杂度
我们需要一个队列,这个队列呢,放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么。
这个队列应该长这个样子:
class MyQueue {
public:
void pop(int value) {
}
void push(int value) {
}
int front() {
return que.front();
}
};
每次窗口移动的时候,调用que.pop(滑动窗口中移除元素的数值),que.push(滑动窗口添加元素的数值),然后que.front()就返回我们要的最大值。
这么个队列香不香,要是有现成的这种数据结构是不是更香了!
其实在C++中,可以使用 multiset 来模拟这个过程,文末提供这个解法仅针对C++,以下讲解我们还是靠自己来实现这个单调队列。
然后再分析一下,队列里的元素一定是要排序的,而且要最大值放在出队口,要不然怎么知道最大值呢。
但如果把窗口里的元素都放进队列里,窗口移动的时候,队列需要弹出元素。
那么问题来了,已经排序之后的队列 怎么能把窗口要移除的元素(这个元素可不一定是最大值)弹出呢。
其实队列没有必要维护窗口里的所有元素,只需要维护有可能成为窗口里最大值的元素就可以了,同时保证队列里的元素数值是由大到小的。
那么这个维护元素单调递减的队列就叫做单调队列,即单调递减或单调递增的队列。C++中没有直接支持单调队列,需要我们自己来实现一个单调队列
不要以为实现的单调队列就是 对窗口里面的数进行排序,如果排序的话,那和优先级队列又有什么区别了呢。
对于窗口里的元素{2, 3, 5, 1 ,4},单调队列里只维护{5, 4} 就够了,保持单调队列里单调递减,此时队列出口元素就是窗口里最大元素。
此时大家应该怀疑单调队列里维护着{5, 4} 怎么配合窗口进行滑动呢?
设计单调队列的时候,pop,和push操作要保持如下规则:
pop(value):如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作
push(value):如果push的元素value大于入口元素的数值,那么就将队列入口的元素弹出,直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则,每次窗口移动的时候,只要问que.front()就可以返回当前窗口的最大值。
#include <vector>
#include <iostream>
#include <deque>
class Solution {
private:
class MyQueue {
public:
std::deque<int> que;
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
int front() {
return que.front();
}
};
public:
std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
MyQueue que;
std::vector<int> result;
for (int i = 0; i < k; i++) {
que.push(nums[i]);
}
result.push_back(que.front());
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i - k]);
que.push(nums[i]);
result.push_back(que.front());
}
return result;
}
};
int main() {
Solution sol;
// 示例数组和窗口大小
std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
// 调用函数并接收结果
std::vector<int> result = sol.maxSlidingWindow(nums, k);
// 打印结果
std::cout << "最大滑动窗口的元素为: ";
for (int num : result) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示:
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的
进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。
创建hash表,每个键对应一个元素,值对应元素出现的次数
这道题目主要涉及到如下三块内容:
要统计元素出现频率
对频率排序
找出前K个高频元素
首先统计元素出现的频率,这一类的问题可以使用map来进行统计。
然后是对频率进行排序,这里我们可以使用一种 容器适配器就是优先级队列。
什么是优先级队列呢?
其实就是一个披着队列外衣的堆,因为优先级队列对外接口只是从队头取元素,从队尾添加元素,再无其他取元素的方式,看起来就是一个队列。
而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢?
缺省情况下priority_queue利用max-heap(大顶堆)完成对元素的排序,这个大顶堆是以vector为表现形式的complete binary tree(完全二叉树)。
什么是堆呢?
堆是一棵完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆,小于等于左右孩子就是小顶堆。
所以大家经常说的大顶堆(堆头是最大元素),小顶堆(堆头是最小元素),如果懒得自己实现的话,就直接用priority_queue(优先级队列)就可以了,底层实现都是一样的,从小到大排就是小顶堆,从大到小排就是大顶堆。
本题我们就要使用优先级队列来对部分频率进行排序。
为什么不用快排呢, 使用快排要将map转换为vector的结构,然后对整个数组进行排序, 而这种场景下,我们其实只需要维护k个有序的序列就可以了,所以使用优先级队列是最优的。
题目要求前 K 个高频元素,那么果断用大顶堆啊。
那么问题来了,定义一个大小为k的大顶堆,在每次移动更新大顶堆的时候,每次弹出都把最大的元素弹出去了,那么怎么保留下来前K个高频元素呢。
而且使用大顶堆就要把所有元素都进行排序,那能不能只排序k个元素呢?
所以我们要用小顶堆,因为要统计最大前k个元素,只有小顶堆每次将最小的元素弹出,最后小顶堆里积累的才是前k个最大元素。
大顶堆(也称为最大堆)是一种特殊的完全二叉树。在这种数据结构中,每个父节点的值都大于或等于其子节点的值。这种属性使得大顶堆的根节点总是包含整个堆中的最大值。以下是大顶堆的一些关键特征:
完全二叉树:大顶堆是一种特殊的完全二叉树,这意味着除了最后一层外,每一层都被完全填满,而最后一层的节点尽可能地集中在左侧。
父节点的值大于子节点的值:在大顶堆中,每个节点的值都大于或等于其子节点的值。这适用于每个非叶子节点。
堆顶元素:由于每个父节点的值都大于其子节点,堆的根节点(或称为堆顶)包含了堆中的最大值。
动态结构:尽管大顶堆是有序的,它并不是完全排序的。当添加新元素或移除堆顶元素时,堆会通过一系列的比较和交换操作(称为堆化)来重新调整结构,以维持大顶堆的性质。
应用场景:大顶堆常用于实现优先队列,以及在各种算法中,如堆排序、查找最大元素等。
在C++中,大顶堆可以使用标准库中的 priority_queue
来实现,而无需指定比较函数,因为 priority_queue
默认就是一个大顶堆。例如:
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> maxHeap;
maxHeap.push(10);
maxHeap.push(5);
maxHeap.push(15);
while (!maxHeap.empty()) {
cout << maxHeap.top() << " ";
maxHeap.pop();
}
return 0;
}
在这段代码中,priority_queue<int>
定义了一个存储整数的大顶堆,堆顶始终是当前堆中的最大值。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
class Solution {
public:
class mycomparison {
public:
bool operator()(const std::pair<int, int>&lhs,const std::pair<int, int>&rhs) {
return lhs.second > rhs.second;
}
};
std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
std::unordered_map<int, int> map; //map<nums[i], times>
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++;
}
//定义一个小顶堆,大小为k
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, mycomparison> pri_que;
//用固定大小为k的小顶堆,扫描所有频率的数值
for (std::unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) {
pri_que.pop();
}
}
//找出前k个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组
std::vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
int main() {
Solution sol;
// 测试数据
std::vector<int> nums = {1, 1, 1, 2, 2, 3,3,3};
int k = 2;
// 调用方法
std::vector<int> topK = sol.topKFrequent(nums, k);
// 输出结果
std::cout << "Top " << k << " frequent elements are: ";
for (int num : topK) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
在你提供的代码片段中,operator()
函数是作为 mycomparison
类的成员定义的。这个操作符重载使得 mycomparison
类成为一个函数对象(也称为仿函数)。这个函数对象被用作 std::priority_queue
的自定义比较器。让我们详细分析这个操作符的功能和作用:
bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
参数: operator()
接受两个 std::pair<int, int>
类型的参数,通常表示队列中的元素。在这个场景中,每个 pair
可能代表了一个值及其出现的频率。
返回值: 该函数返回一个布尔值,这个布尔值基于两个 pair
对象的 second
元素的比较结果。
比较逻辑: lhs.second > rhs.second
。这意味着如果 lhs
的 second
值大于 rhs
的 second
值,则返回 true
;否则返回 false
。
std::priority_queue
中的作用当这个比较器用于 std::priority_queue
时,它决定了队列中元素的顺序。在你的场景中,队列中的元素是 std::pair<int, int>
类型的,通常第一个元素代表实际的值,而第二个元素代表这个值的频率或某种权重。
由于 operator()
是根据 pair
的 second
值来进行比较的,这个优先队列会根据 second
值的大小来组织其元素。由于比较器返回 true
当 lhs.second > rhs.second
,这意味着优先队列实际上是一个最小堆——即 second
值较小的元素会被放在队列的更前面。
在你的 topKFrequent
方法中,这种比较器适合用于找到频率(second
值)最高的 k
个元素。使用这个比较器,优先队列会保持其大小为 k
,并始终弹出具有最小频率的元素。这样,当所有元素都被考虑过后,队列中就剩下了频率最高的 k
个元素。
可以出一道面试题:栈里面的元素在内存中是连续分布的么?
这个问题有两个陷阱:
陷阱1:栈是容器适配器,底层容器使用不同的容器,导致栈内数据在内存中不一定是连续分布的。
陷阱2:缺省情况下,默认底层容器是deque,那么deque在内存中的数据分布是什么样的呢? 答案是:不连续的,下文也会提到deque。
所以这就是考察候选者基础知识扎不扎实的好问题。
在栈与队列系列中,我们强调栈与队列的基础,也是很多同学容易忽视的点。
使用抽象程度越高的语言,越容易忽视其底层实现,而C++相对来说是比较接近底层的语言。
我们用栈实现队列,用队列实现栈来掌握的栈与队列的基本操作。
接着,通过括号匹配问题、字符串去重问题、逆波兰表达式问题来系统讲解了栈在系统中的应用,以及使用技巧。
通过求滑动窗口最大值,以及前K个高频元素介绍了两种队列:单调队列和优先级队列,这是特殊场景解决问题的利器,是一定要掌握的。