拍摄制作宣传片企业,眉山网站优化,一个网站多个域名,泰安人才网最新招聘#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 滑动窗口最大值前 K 个高频… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 滑动窗口最大值前 K 个高频元素总结 滑动窗口最大值
239. 滑动窗口最大值 - 力扣LeetCode
这道题是一道困难题给出一个滑动窗口的长度给出一个数组每次滑动窗口向数组右侧滑动一个元素要求返回一个数组该数组记录的是每次移动滑动窗口所包含的数字中最大的一个分别是什么。 不难想出暴力解法每移动一次遍历一遍窗口记录下来当前最大的数时间复杂度是n*k一共n个数据要遍历k次。那么有没有更好的方法来节省时间呢这时我们的单调队列要登场了 什么是单调队列 单调队列是单调递增的队列或者单调递减的队列但是它和优先级队列的不同之处在于我们设计它的时候主要是要维护大值或者小值而单调递增或递减的排序是进出元素控制的并非主要思路是排序这和优先级队列的区别还是很大的顺便说一下单调队列通常使用双端队列做模板实现而优先级队列底层实现是堆也就是二叉树。 本题我们可以借助双端队列创建一个单调队列因为c里没有现成的单调队列单调队列只需要三个函数一个push一个pop一个求最大值 我们如何每次都弹出最大值呢 其实只是需要我们将最大值调整到队列口处而前面小的数直接pop走其实我们要求的是每次窗口中的最大值所以小数完全没有必要维护直接判断弹出即可push时我们判断队尾有没有数小于要push进来的数如果有全部pop出来因为是在队尾插入所以要对对尾元素做判断在实现pop函数时判断本次要删除的元素队头有没有没有就不删没有的原因是之前push元素时候已经弹出了因为为了保证取最大值的函数每次都取最大一开始直接push前k个元素之后采取push一个元素pop一个元素的规律值得注意的不是每一次都要pop但是每一次都要调用至于具体这一步是否真的pop了在pop函数会自动判断。 为什么会这样呢 原因在于我们设计的单调函数里实现的时候我们需要照顾到弹出最大值这个函数所以我们设计成这样用来方便最大值的弹出而在真正函数调用时候为了保证逻辑上的正确我们每次都要调用pop这个函数判断如果此时我们要删的元素不在队头部那么直接往后走加入新元素即可。
class Solution {
private:class MyQueue { //单调队列从大到小public:dequeint 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:vectorint maxSlidingWindow(vectorint nums, int k) {MyQueue que;vectorint 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) 前 K 个高频元素
347. 前 K 个高频元素 - 力扣LeetCode 这道题是考察优先级队列和语法理解
这道题是一个输出前k个高频元素的题并不是只输出一个。所以我们想到用优先级队列来存取前k个高频元素 那么如何判断哪些是高频元素呢? 我们用unordered_map来存取每个数据出现的次数然后用小顶堆来存取数据。 为什么要用小顶堆而不是大顶堆 我们的思路是定义一个只能存k个元素的堆这样我们只需要维护k个数据减少不必要的浪费。由于哈希存储结果是unordered_map来提高效率所以map里是无序的我们在插入元素时候要按着map依次插入进去而用大顶堆的话大的数据排在前面如果map里还有更大的数据那么之前最大的数据要先被弹出来往复操作最后只剩下频率最低的k个元素。而使用小顶堆那么每次弹出最小元素加进来较大元素最后沉淀下来的是k个高频数据。当然如果使用的是map的话可能就不需要考虑这些问题因为是排好序的。
按着刚才的思路写出代码
class Solution {
public:// 小顶堆class mycomparison {public:bool operator()(const pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second;}};vectorint topKFrequent(vectorint nums, int k) {// 要统计元素出现频率unordered_mapint, int map; // mapnums[i],对应出现的次数for (int i 0; i nums.size(); i) {map[nums[i]];}// 对频率排序// 定义一个小顶堆大小为kpriority_queuepairint, int, vectorpairint, int, mycomparison pri_que;// 用固定大小为k的小顶堆扫面所有频率的数值for (unordered_mapint, int::iterator it map.begin(); it ! map.end(); it) {pri_que.push(*it);if (pri_que.size() k) { // 如果堆的大小大于了K则队列弹出保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素因为小顶堆先弹出的是最小的所以倒序来输出到数组vectorint result(k);for (int i k - 1; i 0; i--) {result[i] pri_que.top().first;pri_que.pop();}return result;}
};注意:把map的两个数据都放到堆里然后根据二元组的第二个关键词来进行排序这样我们在进行最后一步转化为数组的时候才能根据频率找到对应的数据缺一不可
总结
今天我们完成了滑动窗口最大值、前 K 个高频元素两道题目相关的思想需要多复习回顾。接下来我们继续进行算法练习·。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
