题目描述

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

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

样例

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

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

算法1

(单调队列、deque)

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    vector<int> maxInWindows(vector<int>& A, int k) {
        deque<int> dq;
        vector<int> res;
        for(int i = 0; i < A.size(); i ++)
        {
            if(dq.size() && dq.front() < i - k + 1) dq.pop_front();
            while(dq.size() && A[dq.back()] < A[i]) dq.pop_back();
            dq.push_back(i);
            if(i >= k - 1) res.push_back(A[dq.front()]);
        }

        return res;
    }
};