题目描述

数组模拟单调队列

算法1

$O(n)$ (暴力枚举方法为$O(nk)$)

C++ 代码

class Solution {
public:
    static const int N=1e2;
    int q[N];
    vector<int> maxInWindows(vector<int>& nums, int k) {
        int h=0,b=-1;
        vector<int> ret;
        for(int i=0;i<nums.size();i++)
        {
            while(h<=b&&q[h]<=i-k) h++;
            while(h<=b&&nums[q[b]]<=nums[i]) b--;
            q[++b]=i;
            if(i>=k-1)
                ret.push_back(nums[q[h]]);

        }
        return ret;
    }
};

算法2

$O(n)$

deque单调队列

C++ 代码

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> ret;

        for(int i=0;i<nums.size();i++)
        {
            while(q.size()&&q.front()<=i-k)  q.pop_front();//判断队列是否在滑动窗口内
            while(q.size()&&nums[q.back()]<=nums[i])  //维持队列的递减性
                q.pop_back();
            q.push_back(i);//防止队列为空要先插入
            if(i>=k-1)
                ret.push_back(nums[q.front()]);//
        }
        return ret;

    }
};