LeetCode 239. 滑动窗口大值
10年积累的网站建设、成都做网站经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先建设网站后付款的网站建设流程,更有建德免费网站建设让你可以放心的选择与我们合作。题目描述:给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的大值 。
视频讲解https://www.bilibili.com/video/BV1XS4y1p7qj/?vd_source=f98f2942b3c4cafea8907a325fc56a48文章讲解https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
class Solution {
private:
// 单调队列(从大到小)
class MyQueue {
public:
// 用deque来实现
dequeque;
// 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。
// 同时pop之前判断队列当前是否为空。
void pop(int val) {
if (!que.empty() && val == que.front()) {
que.pop_front();
}
}
// 如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int val) {
while (!que.empty() && que.back()< val ) {
que.pop_back();
}
que.push_back(val);
}
// 查询当前队列里的大值 直接返回队列前端也就是front就可以了。
int getMax() {
return que.front();
}
};
public:
vectormaxSlidingWindow(vector& nums, int k) {
MyQueue que;
// 滑动窗口大值序列
vectorresult;
// 先将前k的元素放进队列
for (int i = 0; i< k; ++i) {
que.push(nums[i]);
}
result.push_back(que.getMax());
// 移动滑动窗口
for (int i = k; i< nums.size(); ++i) {
que.pop(nums[i - k]);
que.push(nums[i]);
result.push_back(que.getMax());
}
return result;
}
};
LeetCode 347.前 K 个高频元素
题目描述:给定一个非空的整数数组 nums,返回其中出现频率前 k 高的元素。
视频讲解https://www.bilibili.com/video/BV1Xg41167Lz文章讲解https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
// 时间复杂度:O(nlogk)
// 空间复杂度:O(n)
class Solution {
public:
// 小顶堆
class mycomparison {
public:
bool operator()(const pair& lhs, const pair& rhs) {
// 频率低的优先级高
return lhs.second >rhs.second;
}
};
vectortopKFrequent(vector& nums, int k) {
// 要统计元素出现频率
unordered_mapmap; // mapfor (int i = 0; i< nums.size(); i++) {
map[nums[i]]++;
}
// 对频率排序
// 定义一个小顶堆,大小为k
priority_queue, vector>, mycomparison>pri_que;
// 用固定大小为k的小顶堆,扫面所有频率的数值
for (unordered_map::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() >k) { // 如果堆的大小大于了K,则队列弹出,保证堆的大小一直为k
pri_que.pop();
}
}
// 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组
vectorresult(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
总结
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享题目:代码随想录算法训练营第十三天-创新互联
新闻来源:/article48/dgcchp.html
成都网站建设公司_创新互联,为您提供品牌网站建设、全网营销推广、搜索引擎优化、网站营销、品牌网站设计、定制网站
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联