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;
}
};
原创文章，作者：wure，如若转载，请注明出处：https://blog.ytso.com/278571.html