【无标题】

• • • • 暴力做法
      • 单调队列
      • 题目来源

直接遍历所有的滑动窗口，分别判断最大值。

时间复杂度O(n * k)
空间复杂度O(n)

class Solution {
public:
    // 时间复杂度O(n * k)
    // 空间复杂度O(n)
    vector maxInWindows(vector& nums, int k) {
        vector ans;
        for (int i = 0; i <= nums.size() - k; i ++) {
            int temp = getMax(nums, i, k);
            ans.push_back(temp);
        }
        return ans;
    }
    
    int getMax(vector& nums, int start, int k) {
        int res = -0x3f3f3f3f;
        for (int i = start; i < start + k; i ++) {
            res = max(res, nums[i]);
        }
        return res;
    }
    
};

根据滑动窗口的概念，不停往前移动，这是队列的性质：每次队头删掉，队尾入队。所以，用队列来维护滑动窗口。

使用stl 双端队列deque。

每个滑动窗口只需要保留最大值。
时间复杂度O(n)
空间复杂度O(n)

class Solution {
public:
    vector maxInWindows(vector& nums, int k) {
        vector res;
        deque q;
        for (int i = 0; i < nums.size(); i ++) {
            // 如果 当前元素下标 - 队头元素下标 大于等于窗口值，则队头出队
            if (q.size() && i - q.front() >= k) q.pop_front();
            // 当前窗口中只需要保留最大值
            while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();
            // 每个元素下标入队
            q.push_back(i);
            // 每个滑动窗口输出一个最大值
            if (i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

https://www.acwing.com/problem/content/75/