题目描述

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。

例如，如果输入数组[2, 3, 4, 2, 6, 2, 5, 1]及滑动窗口的大小3,那么一共存在6个滑动窗口，它们的最大值分别为[4, 4, 6, 6, 6, 5]。

注意：

数据保证k大于0，且k小于等于数组长度。

样例

输入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

时间复杂度

O(n)

参考文献

C++ 代码

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q;
        for(int i = 0; i < nums.size(); i++)
        {
            while(q.size() && q.front() <= i - k) q.pop_front();//弹出窗口之外的数，
            while(q.size() && nums[i] >= nums[q.back()]) q.pop_back();//当前数大于队尾元素，队尾元素就永远用不上，删除
            q.push_back(i);//当前元素加入队尾
            if(i >= k - 1) res.push_back(nums[q.front()]);//当遍历到k-1个数时，在结果数组中加入最大值
        }
        return res;
    }
};