这是开学以来的第一篇题解，为了保持一定的手感，除了周末，每天保证更新一篇题解。

原题链接

ACwing

思路

题意十分简单，为数组的每一个固定长度的区间维护一个最大值。最为朴素的做法就是直接求解最大值，不过这样没有用上“滑动”的性质，是否可以边扫描数组，边维护数组的每一个最大值？

仔细思考，对于每一个区间中的数字，如果其右边的数字比其来的大，那么当前数字实际上一定不会在之后的大小比较中出现（当前数字一定先离开窗口），这启发我们维护一个值、ind的二元组队列，并且按照值单调减排列，这也就是传说中的单调队列。

维护单调队列的方法十分简单：

  1. 在每一个区间中，丢弃所有不在当前窗口的元素；
  2. 对于每一个区间中新加入的元素，如果当前队列非空，比较其与队尾元素的大小，如果其比队尾元素大，那么丢弃队尾元素，执行2；否则执行3；
  3. 将当前的元素加入队列中。

实现

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
class Solution {
public:
    deque<pair<int,int> > mono_q;
    
    void add(int x, int ind){
        while(mono_q.size()&&x>mono_q.back().first){
            mono_q.pop_back();
        }
        mono_q.push_back(pair(x,ind));
    }
    
    void pop(int lhs){
        while(mono_q.size()&&mono_q.front().second<lhs)mono_q.pop_front();
    }
    
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> ans;
        // init the queue 
        for(int i=0;i<k-1;i++){
            add(nums[i],i);
        }
        
        // traverse all intervals
        for(int lhs = 0;lhs+k-1<nums.size();lhs++){
            pop(lhs);// pop all the elements which are out of window
            add(nums[lhs+k-1], lhs+k-1);
            ans.push_back(mono_q.front().first);
        }
        
        return ans;
    }
};