【每日一题】3月30日题目精讲 单调队列

题号 NC50528
名称 滑动窗口

滑动窗口取最值问题是一个非常经典的问题,当然你可使用线段树树状数组ST表等等方法去求,我在这里呢给大家介绍一种时间复杂度,简单实在将来也有很多地方能用的方法——单调队列。

以求最大值为例:

区间的最大值为:

区间右移到后最大值为:

我们可以看到这两段区别仅仅在 上,扫一遍显然是很没必要的。而如果 ,那么当进入了窗口中,就不可能作为最大值存在了,如果我们记录当前区间中现在或者将来有机会成为最大值的数,那么就可以从这个记录中删掉了。如果, 当出了区间,还是有机会的,所有需要留着。


我们用一个双端队列来维护(普通的队列只能从队尾加入元素从队首删除元素,双端队列的队尾也可也删除元素),区间每次右移一个单位,首先看看队首的元素是否超出了范围,如果超出了,就把它删掉;然后将新进入区间的这个元素往双端队列里放,但放进来之前需要判断队尾(也就是还有可能成为最大值的最后一个元素)是不是小于他小于他,如果是,就把这个队尾删掉,一直到前一个元素大于等于它为止。由于我们队列里面的元素实际上是单调不增的,每次的最大实际上就在队首。而由于每个数进队和出队的次数都只有一次,时间复杂度是的。

标程是手工用数组模拟的双端队列,你也可以使用stl里的deque容器。

看完邓老师的题解,记得自己去做题提高呀~
欢迎各位大佬来做题写题解,也欢迎大家踊跃在本讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得10-50牛币(依据题目难度和题解的内容而定)

本道题目4月6日中午12:00之前写的题解有获得牛币资格~

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/790eb8582b494c0dbe12ed1795482c3a
1 回复 分享
发布于 2020-05-02 22:52
如何判断队首元素超出区间范围
1 回复 分享
发布于 2020-03-30 14:19
https://blog.nowcoder.net/n/0bf61afa71294bd1ab2e37ab14f1fc15
点赞 回复 分享
发布于 2020-06-28 13:49
https://blog.nowcoder.net/n/2a3f2026d5c54695b6dbdb76f1a8484f
点赞 回复 分享
发布于 2020-06-27 16:11
https://blog.nowcoder.net/n/d4c7a5f7e9a04e0a97a9e9f25c2167ae
点赞 回复 分享
发布于 2020-06-26 10:28
https://blog.nowcoder.net/n/bb2de202ce8c461887b387e7036c35d0
点赞 回复 分享
发布于 2020-05-05 10:28
https://blog.nowcoder.net/n/d49497c047cc4e2580f29c7d75fdbf1a
点赞 回复 分享
发布于 2020-05-04 22:24
https://blog.nowcoder.net/n/efafddf5b148489fab6fb7eace56903e
点赞 回复 分享
发布于 2020-05-02 16:17
https://blog.nowcoder.net/n/2b7fca8e03d1410a965fd0a74f216566
点赞 回复 分享
发布于 2020-05-02 10:21
https://blog.nowcoder.net/n/80367b96abff43898b1da5a310668798
点赞 回复 分享
发布于 2020-05-01 15:16
补发题解https://blog.nowcoder.net/n/8152b1e72c334dd1976716b05a97f124
点赞 回复 分享
发布于 2020-05-01 13:13
https://blog.nowcoder.net/n/2ee92f792bb24ddaa9237bcae7016992
点赞 回复 分享
发布于 2020-04-05 20:57
https://blog.nowcoder.net/n/036ea47792ba44848ce916a564ff83f4
点赞 回复 分享
发布于 2020-04-02 18:42
https://blog.nowcoder.net/n/39197627317b45019b45420ca0013687
点赞 回复 分享
发布于 2020-04-02 17:04
https://blog.nowcoder.net/n/905605271b6046c8a139ec9856ec987a
点赞 回复 分享
发布于 2020-04-02 14:42
https://blog.nowcoder.net/n/b3ceffb0d2a640abac5198e4dc796dc5
点赞 回复 分享
发布于 2020-04-02 14:32
https://blog.nowcoder.net/n/6bcd1fbf211746dbb924296a71b2e9e9   第一次写博客,希望能坚持下去,欧力给
点赞 回复 分享
发布于 2020-04-02 12:13
https://blog.nowcoder.net/n/bcef9dd0f86e48c2a2f23448c6435a17
点赞 回复 分享
发布于 2020-04-02 07:10
https://blog.nowcoder.net/n/1836433a65d84432b69fc6734225d592今天的题解
点赞 回复 分享
发布于 2020-03-30 19:25
https://blog.nowcoder.net/n/6f99f531a2e34c978f5ca1dbd3cb0d40
点赞 回复 分享
发布于 2020-03-30 18:14

相关推荐

04-16 10:27
已编辑
美团_Saas_后端开发
今天周一休息,突发奇想写一篇阶段总结。如题,我已经去了一个和Java彻底毫无关联的行业。曾经我以为自己能在计算机行业发光发热,拿到美团offer那会感觉自己天都亮了。没想到刚入行一年多就当了逃兵。从最开始的热爱到现在一看到代码就厌恶,不知道自己经历了什么。所以我去干什么了?答案是:在成都当了租房销售。上班那会压力大了就念叨着去干租房中介,但是一直下不去这个决心,想着自己学了四年多的计算机知识,终究还是不甘心。终于在某一天准备八股文的时候,看着无数篇和工作内容关系不大的理论知识,那一刻下定决心,决定尝试一下销售行业,也算是给自己一个交代。后面阴差阳错的投了成都自如去当租房管家,没想到面试很顺利,在当天一百多个面试的人里面,我成为了为数不多通过的几个幸运儿之一。目前已经培训通过,正式入职,也开了单,有压力但是每天过得很开心,真心喜欢那种和人交流的感觉,哪怕是最后没有选择找我租房。说这些也是想告诉那些大三,大四正在找Java实习而焦虑的同学:你们现在还年轻,选择很多,容错率也很高,可以尽情去尝试自己喜欢的行业和工作。不用因为某一次的面试没通过或者简历石沉大海而焦虑,更不用因为身边人都在挤编程的独木桥就强迫自己跟风。也算是自己的碎碎念吧,也希望自己能在新的领域取得一点小成就。也祝牛油工作顺利!
沉淀小子:干啥都不丢人啊,生存是必须要的,销售很考验一个人综合素质能力的,好的销售人脉和资源可不比写字楼的白领差啊
点赞 评论 收藏
分享
03-28 16:43
佛山大学 Java
java全国可飞:简历2.0,各位佬看看,这样可以吗查看图片
点赞 评论 收藏
分享
评论
5
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务