239.滑动窗口的最大值
程序员文章站
2024-03-19 22:19:10
...
正确的解法是使用双端队列来处理这个window的功能。
c++ deque有现成的stl可以使用
需要注意几个点
1. 需要维护队列内部的最大值在队首的位置,每次想要添加一个新元素的时候就循环和前面的元素做比较
2. 判断一个元素是否过期,可以直接用当前队首和应该淘汰的数字进行对比如果一致就去除
主要逻辑:
1. 如果该数据小于新加入的数据,再上一步就应该被清除所以不需要考虑过期的问题
2. 如果当前的数据大于新加入的数据,但是又恰好等于i -k这个位置的数据,那么在确定最大值之前就需要将它清理出来
/*
* @lc app=leetcode.cn id=239 lang=cpp
*
* [239] 滑动窗口最大值
* 使用deque双端队列的方法来解决,效率比较低
*/
// @lc code=start
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if(nums.size() < 1) return vector<int>();
if(k == 1) return nums;
if(nums.size() <= k) return vector<int>{ *std::max_element(nums.begin(),nums.end())};
vector<int> ret;
deque<int> window;
window.push_front(nums[0]);
for (int i = 1; i < nums.size() ; i++) {
//这里面有一个循环剔除前面所有的数据
while (window.size() > 0 && nums[i] > window.back()) {
window.pop_back();
}
window.push_back(nums[i]);
//window front用来判断是否是过期的数据,如果有重复数据也应该被前面循环所去除
if (i >= k && window.front() == nums[i - k]) {
window.pop_front();
}
if (i >= k - 1) {
ret.push_back(window.front());
}
}
return ret;
}
};
// @lc code=end
deque的性能确实不怎么的,如果可以还是用数据效率比较高,但是容器就是胜在了方便