leetcode-滑动窗口的最大值-95

题目要求

思路
1.这个题是可以暴力求解的，但是时间复杂度比较高，因此，这里说一个时间复杂度为O(n)的方法
2.因为这个代码是优化后的结果，第一次写如果直接写成这样着实不容易，因此，我直接讲每一行的含义。
3.创建一个数组ans，这个用来存储最终返回的最大值的结果
4.创建一个双端队列dq，这个里面存储是num中元素的下标
5.首先如果dq为空，那么我们先插入一个第一个元素的下标
6.第二个while循环，如果新来的这个元素的值大于之前元素的值，那么新来的这个值只要没出去，前面的比他小的值都需要被覆盖，目的就是让num[dq[i]]的值是单调递减的
6.第一个while循环，用于模拟滑动窗口的左端，如果该元素从左边已经滑出，那么需要更新双端队列的队头
7.将满足滑动窗口中最大的值，也就是存储在dq中的front的下标的值，保存到ans中，最后返回ans。
总结：这个题代码行数虽然不多，但是着实不好一次写对，算是一个比较重要的题，值得深思。

代码实现

class Solution {
public:
    vector<int> maxInWindows(vector<int>& num, int size) {
        vector<int> ans;
        deque<int> dq; //用于存储下标
        for(int i = 0; i < num.size(); i++)
        {
            while( !dq.empty() && i - dq.front() + 1 > size)
                dq.pop_front();
            while(!dq.empty() && num[dq.back()] <= num[i])
                dq.pop_back();
            dq.push_back(i);
            if(size && i >= size - 1)
                ans.push_back(num[dq.front()]);
        }
        return ans;
    }
};