type
status
date
slug
summary
tags
category
icon
password
10/20
从甜蜜的周末里来到第一题
📝 题目信息
大概就是说: 你要求出每一个长度为M的区间的最小值
🤗 走了不少弯路，一开始就想暴力
最开始用了很普通的双指针,但是发现TLE了很多,一看数据范围(10^6),看看我的代码,
O(N MlogM),这不超时才怪,所以Google了一下发现有一个非常巧妙的方法⬇️
—单调队列—
定义:
- 【单调】 + 【队列】:
- 要把所有在这个队列里面大于它的数都弹出队列
- 这样就保证了队首元素是窗口的最小值
- 判断队首元素是否在窗口内部
利用单调队列求解滑动窗口的最值问题！
代码里面有解释
时间复杂度分析
- 这样只需要遍历一次列表就可以求出每个窗口的最值 → O(N) N是列表长度
😭 总结反思:
暴力不可取,还是多学一点有用的结构吧 qwq单调队列 - OI Wiki
📎 参考文章
欢迎您在底部评论区留言，一起交流~
- 作者:PanDa
- 链接:Panda_Clog | 代码Vlog (c.pandaclog.xyz)/article/1250312b-e533-80b6-85a4-e0097b468c08
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
