leetcode 滑动窗口的最大值 困难
2021/8/27 6:09:09
本文主要是介绍leetcode 滑动窗口的最大值 困难,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
查询区间最大值,解法挺多的:线段树,RMQ 都可。不过都是 O(nlogn)
单调队列:O(n),注意 i >= k - 1 才加入答案,以及 pop_front 的条件是 .front() <= i - k
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> deq; // 单调队列 vector<int> ret; for(int i = 0; i < nums.size(); ++ i) { while(!deq.empty() && deq.front() <= i - k) deq.pop_front(); while(!deq.empty() && nums[deq.back()] < nums[i]) deq.pop_back(); deq.push_back(i); if(i >= k - 1) ret.push_back(nums[deq.front()]); } return ret; } };
这篇关于leetcode 滑动窗口的最大值 困难的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-23云原生周刊:Artifact Hub 成为 CNCF 孵化项目|2024.9.23
- 2024-09-22为啥chrome查看到网页,只有5000多行,应该有1万多行才对
- 2024-09-21LangChain4j支持的API类型
- 2024-09-21企业如何判断自身的 CRM 系统需要多大的服务器配置?
- 2024-09-21拼接的xml报文,尖括号都被转移成了< 是什么原因-icode9专业技术文章分享
- 2024-09-21Svg Sprite Icon教程:从入门到实践
- 2024-09-21Svg Sprite Icon实战:从入门到上手
- 2024-09-20构建一个多PDF RAG聊天机器人:使用Langchain和Streamlit及代码
- 2024-09-20whatsapp webhook 回调的签名验证偶尔会失败是什么原因-icode9专业技术文章分享
- 2024-09-19Excel数据导出课程:初学者必备教程