响应式自适应网站,雄安智能网站建设电话,宝洁公司网站建设现状,互联网推广营销都选隐迅推239. 滑动窗口最大值 - 力扣#xff08;LeetCode#xff09;
每次只取窗口中最大值#xff0c;这个最大值可能在后面的滑动中保持不变#xff0c;而比最大值小的值且在最大值之前出现的值没必要保留#xff0c;因此可以通过单调队列利用这个特性。
这个单调队列具有如下…239. 滑动窗口最大值 - 力扣LeetCode
每次只取窗口中最大值这个最大值可能在后面的滑动中保持不变而比最大值小的值且在最大值之前出现的值没必要保留因此可以通过单调队列利用这个特性。
这个单调队列具有如下性质:
1.队头始终为当前队列的最大值
2.队列具有单调性队尾为最小值
因此用三个函数实现题目要求。
pop()检查当前滑动窗口最后一个元素是否为单调队列的队头若不是则不用管这说明该元素不是当前单调队列的最大值在这之前就已经被丢出单调队列中。
push()将当前滑动窗口的第一个元素加入单调队列中把队列中小于该元素的值全部丢出队列。
getmax()单调队列的队头即为最大值。
class Solution {
private:class MyQueue{public:dequeint queue;void pop(int num){if(!queue.empty() num queue.front())queue.pop_front();}void push(int num){while(!queue.empty() num queue.back()){queue.pop_back();}queue.push_back(num);}int getMax(){return queue.front();}};
public:MyQueue queue;vectorint maxSlidingWindow(vectorint nums, int k) {vectorint res;for(int i 0; i k; i){queue.push(nums[i]);}res.push_back(queue.getMax());for(int i k; i nums.size(); i){queue.pop(nums[i - k]);queue.push(nums[i]);res.push_back(queue.getMax());}return res;}
};
