题目

• 给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。
• 例如，如果输入数组 [2, 3, 4, 2, 6, 2, 5, 1] 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，它们的最大值分别为 [4, 4, 6, 6, 6, 5]。
• 数据范围

数组长度 [1, 1000]。

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

示例

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

代码

• $O(k*n)$

class Solution {
public:
    vector<int> res;
    int getMax(vector<int>& v ,int l, int r){
        int max = 0;
        while(l <= r){
            if(v[l] > max) max = v[l];
            l++;
        }
        return max;
    }
    vector<int> maxInWindows(vector<int>& nums, int k) {
        int l = 0, r = k - 1;
        int max = getMax(nums, l, r);
        while(r < nums.size()){
            res.push_back(max);
            l++, r++;
            if(nums[r] > max)   max = nums[r];
            else if(nums[l-1] == max){
                max = getMax(nums, l , r);
            }
        }
        return res;
    }
};

代码分析：大早上 AC 一道题，心情还是很爽的。用的时空复杂度也都不算高，我是能接受的

• 单调队列

【视频讲解】

题目：滑动窗口的最大值