首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
彭三岁
字节跳动_服务端开发
发布于北京
关注
已关注
取消关注
@牛客题解官:
滑动窗口的最大值
描述 这是一篇针对初学者的题解。共用两种方法解决。从暴力算法一步步到最优算法。知识点:数组,队列难度:二星 题解 题目描述:给定一个数组num和一个窗口大小size,求每个窗口的最大值。 方法一:暴力方法 根据题目描述,我们很容易想到暴力方法。并且也很轻松的就可以写出来。如果数组的大小是n,窗口的大小是size,那么窗口的数量就是 n - size + 1.算法步骤如下: 枚举每个窗口的左边界 i 根据窗口的左边界i可以对应计算出右边界j 遍历窗口,计算出最大值 代码如下: class Solution {public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<int> ret; if (num.size() == 0 || size < 1 || num.size() < size) return ret; int n = num.size(); for (int i = 0; i + size - 1 < n; ++i) { int j = i + size - 1; int max_val = num[j]; for (int k = i; k < j; ++k) { max_val = max(max_val, num[k]); } ret.push_back(max_val); } return ret; }};时间复杂度:O(n*k), 其中n为数组大小,k为窗口大小空间复杂度:O(1),存结果必须要开的数组不算入额外空间 方法二:单调队列 方法一种存在很多大量重复计算,比如说,对于数组,假设我们当前遍历到下标i,对于下标i+1的元素(假设i和i+1都在同一个窗口),如果比arr[i]大,说明了什么?如果arr[i+1] 已经大于了 arr[i], 那么还要arr[i]有什么用.就有点“既生瑜何生亮”的感觉。如果arr[i+1] < arr[i]呢?显然arr[i]还是需要保留的。为什么呢?因为又可以arr[i] 对于下一个arr[i+1]所在的窗口来说,arr[i]已经失效了。 假设这里有那么一个容器可以保留上述操作。 遍历数组的每一个元素, 如果容器为空,则直接将当前元素加入到容器中。 如果容器不为空,则让当前元素和容器的最后一个元素比较,如果大于,则将容器的最后一个元素删除,然后继续讲当前元素和容器的最后一个元素比较 如果当前元素小于容器的最后一个元素,则直接将当前元素加入到容器的末尾 如果容器头部的元素已经不属于当前窗口的边界,则应该将头部元素删除 总结一下,首先容器中放的元素应该是单调递减的。然后还有删除容器头部元素和最后一个元素的操作。因此,这样的数据结构就是双端队列。c++中就是deque 如何判断队列中头部的元素是否过期呢?这里我们可以存数组的下标,根据下标的比较来判断。比如,当前遍历到下标为5的元素,窗口的大小为3, 显然显然下标为2的已经过期了。 代码如下: class Solution {public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<int> ret; if (num.size() == 0 || size < 1 || num.size() < size) return ret; int n = num.size(); deque<int> dq; for (int i = 0; i < n; ++i) { while (!dq.empty() && num[dq.back()] < num[i]) { dq.pop_back(); } dq.push_back(i); // 判断队列的头部的下标是否过期 if (dq.front() + size <= i) { dq.pop_front(); } // 判断是否形成了窗口 if (i + 1 >= size) { ret.push_back(num[dq.front()]); } } return ret; }};时间复杂度:O(n), 其中n为数组大小空间复杂度:O(k),k为窗口的大小
点赞 96
评论 8
全部评论
推荐
最新
楼层
滴滴
校招火热招聘中
官网直投
相关推荐
充满希望的柯基
今天 11:49
华中科技大学 电子信息类
不知道暑期实习该何去何从
从4.10开始投,有两个大厂是进了hr面然后被排序挂了。到五月之后明显感觉约面的变少了,五月投了好多中厂但是流程迟迟不推进,做了笔试或者测评之后就一直没消息了。不知道现在该咋办…
我的实习求职记录
点赞
评论
收藏
转发
lao_yan
05-16 16:37
已编辑
金山WPS_Android开发实习生(准入职员工)
5.15腾讯cisg客户端一面,高攀不起(居然过了)
面试官说是这个那个确实有点超纲,问的是一个比一个重量级,还非要面快俩小时,记录一下这次5分无语4.9分崩溃0.1分搞笑的面试。1. 一上来没说开摄像头,我已经有点意识到不妙了,面试官问了下base有没有要求和实习时间。2. 问实习,热更新项目如何写的,JSON如何映射成原生组件,项目整体框架,流程,我负责的部分,扯了20分钟,问一些极限情况的处理办法,我……3. Android的xml布局文件支持不编译就可以看到样式,你们的这个支持吗(不支持)4. 支持增量下载吗(???)5. 下载可能失败,你们处理方式是什么(……)6. 自定义控件可以通过设置margin padding改变位置吗,是怎么做...
查看60道真题和解析
点赞
评论
收藏
转发
19190
05-02 10:18
已编辑
河南大学 土木类
是的,学土木的,是的找不到工作实习。。
有没有改简历的神给评价一下目前0OFFER请问大神们我可以用这个投市场营销,公关之类的岗位吗,还是再搞个简历呢 #最后再改一次简历# #你的简历改到第几版了# #24应届#
最后再改一次简历
你的简历改到第几版了
点赞
评论
收藏
转发
已经没有头给你虾了
05-16 11:34
已编辑
字节跳动Data部门三面面经 (社招)
自我介绍介绍项目Mysql为啥用B+树有哪些数据库用的B树当时你们公司自研的那个DB里面索引介绍一下你们公司自研的那个DB怎么判断一个key写到哪个分区一个sql的join语句在MapReduce中的执行过程是怎样的做题,大数相加一面传送门:https://www.nowcoder.com/discuss/619624955755446272?二面传送门:https://www.nowcoder.com/discuss/619603839406174208答的依托答辩,面前不努力,面后靠锦鲤。求求来个offer吧-----------------------------------------...
查看6道真题和解析
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
因为找实习和女朋友分手了
1.2W
2
...
开摆了,写小说去了
7723
3
...
【有奖活动】浅聊一下我的实习⭐
7538
4
...
双非本 腾讯WXG暑期已offer | 附面经
7354
5
...
没offer的我们也很优秀偶
7307
6
...
华为暑期开奖
6285
7
...
滴滴秋储-服务端开发 OC
4744
8
...
华为实习offer!终于告一段落了
4627
9
...
写在最后,一个大专人9年的自述
4403
10
...
真有必要读研吗
4349
正在热议
#
牛客帮帮团来啦!有问必答
#
828083次浏览
13079人参与
#
机械制造薪资爆料
#
320671次浏览
3738人参与
#
晒一晒我的offer
#
3474332次浏览
55304人参与
#
金三银四,你有感觉到吗
#
329960次浏览
4227人参与
#
0offer是寒冬太冷还是我太菜
#
428861次浏览
4950人参与
#
海康威视求职进展汇总
#
101983次浏览
1218人参与
#
实习生如何通过转正
#
27098次浏览
361人参与
#
我在牛爱网找对象
#
50542次浏览
331人参与
#
实习生应该准时下班吗
#
81036次浏览
595人参与
#
软件开发投递记录
#
479588次浏览
7248人参与
#
如果可以选,你最想从事什么工作
#
186567次浏览
3086人参与
#
求职遇到的搞笑事件
#
19740次浏览
287人参与
#
实习必须要去大厂吗?
#
14010次浏览
223人参与
#
你觉得找工作该拿大厂还是小厂练手
#
61885次浏览
873人参与
#
荣耀求职进展汇总
#
71144次浏览
722人参与
#
你的秋招进行到哪一步了
#
369103次浏览
6403人参与
#
你觉得通信/硬件有必要实习吗?
#
23659次浏览
428人参与
#
国企vs私企,你更想去?
#
20324次浏览
205人参与
#
你觉得今年秋招难吗
#
311743次浏览
5795人参与
#
正在春招的你,也参与了去年秋招吗?
#
136568次浏览
1707人参与
牛客网
牛客企业服务