LeetCode 239 Sliding Window Maximum 单调队列 [Hard]
2022/8/3 6:52:48
本文主要是介绍LeetCode 239 Sliding Window Maximum 单调队列 [Hard],对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
You are given an array of integers nums
, there is a sliding window of size \(k\) which is moving from the very left of the array to the very right. You can only see the \(k\) numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Solution
求出在每个窗口的最大值。我们使用单调队列 \(O(n)\),具体来说:
假设在位置 \(i\), 我们维护的区间为 \([i-k+1, i]\). 我们的单调队列维护的是下标 \(idx\),所以如果队首的下标满足:
\[q.front<i-k+1 \]则说明不在当前区间内,则 \(pop\) 出去。
由于我们只需要维护最大值,所以比当前元素小的都得 \(pop\_back()\)
点击查看代码
class Solution { private: vector<int> ans; deque<int> q; public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n=nums.size(); for(int i=0;i<n;i++){ // [i-k+1, i]: #ele = i-(i-k+1)+1 = k; if(q.front()<i-k+1 && !q.empty()) q.pop_front(); while(!q.empty() && nums[q.back()]<nums[i])q.pop_back(); q.push_back(i); if(i-k+1>=0)ans.push_back(nums[q.front()]); } return ans; } };
这篇关于LeetCode 239 Sliding Window Maximum 单调队列 [Hard]的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!