Leetcode_239. 滑动窗口最大值

单调队列模板题，扫描一遍，队尾维护单调性，队头维护不超过大小为k的区间。

code

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> q(n+5,0);
        int l=0,r=-1;
        vector<int> ans;
        for(int i=0;i<n;i++){
            while(r-l+1!=0 && nums[q[r]]<nums[i]){
                r--;
            }
            q[++r]=i;
            while(r-l+1!=0 && q[l]+k<=i){
                l++;
            }
            if(i>=k-1){
                ans.push_back(nums[q[l]]);
            }
        }
        return ans;
    }
};

Leetcode_239. 滑动窗口最大值

原文：https://www.cnblogs.com/zxcoder/p/12629701.html