单调队列解题思路

1.使用双端队列
2.维护队列的单调性，保持由大到小，队头即为当前窗口的最大元素，将小于nums[i]的元素全部pop
3.注意最大值必须要在当前窗口的范围内

deque代码(记录数组的索引)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {     
        vector<int> res;
        deque<int> dq;
        for (int i = 0; i < nums.size(); i++) 
        {
            while(!dq.empty() && nums[dq.back()] < nums[i])   dq.pop_back();      //保持单调性
            if(!dq.empty() &&  dq.front() == i-k)    dq.pop_front();     //检查最大值是否超出窗口范围
            dq.push_back(i);
            if(i >= k-1)    res.push_back(nums[dq.front()]);
        }        
        return res;
    }
};

deque代码(记录数组的元素)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {     
        vector<int> res;
        deque<int> dq;
        for (int i = 0; i < nums.size(); i++) 
        {
            while(!dq.empty() && dq.back() < nums[i])   dq.pop_back();      //保持单调性
            if(!dq.empty() && i >= k && dq.front() == nums[i-k])    dq.pop_front();     //检查最大值是否超出窗口范围
            dq.push_back(nums[i]);
            if(i >= k-1)    res.push_back(dq.front());
        }        
        return res;
    }
};

手写类(思路一样)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MonotonicQueue{
private:
    deque<int> data;
public:
    void push(int n)
    {
        while(!data.empty() && data.back() < n)
            data.pop_back();
        data.push_back(n);
    }

    int max()   {return data.front();}

    void pop(int n)
    {
        if(!data.empty() && data.front() == n)
            data.pop_front();
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        MonotonicQueue window;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(i < k-1)     window.push(nums[i]);
            else
            {
                window.push(nums[i]);
                res.push_back(window.max());        //将本轮窗口的最大值加入res中
                window.pop(nums[i+1-k]);            //检查最大值是否将要滑出范围
            }
        }
        return res;
    }
};