题解 | #滑动窗口的最大值#

滑动窗口的最大值

1、题意重述

给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。

换句话说，即一个滑动窗口在数组上进行滑动，求出窗口在每个位置时对应数组中元素的最大值。

2、思路整理

使用双指针的思想：

Step1:选取两个指针，分别为l，r指针，通过l指针的位置和滑动窗口的大小，计算出r指针的位置。

Step2：对l，r指针内的元素进行求最大值操作，并进行记录。

Step3：将l指针右移，重复Step1和Step2的操作，最终得到答案。

3、代码实现

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> ans;
        for(int l = 0; l < num.size() - size + 1; l ++ ) { //固定l指针
            int r = l + size - 1;                          //计算r指针
            int maxn = -1;
            for(int i = l; i <= r; i ++ ) maxn = max(maxn, num[i]); //求最大值
            if(maxn != -1) ans.push_back(maxn);            //保存结果
        } 
        return ans; //返回题目所需答案
    }
};

4、复杂度分析

时间复杂度：遍历数组加滑动窗口内求最大值，因此时间复杂度为$O(Nk)O(Nk)$，其中N为数组长度，k为滑动窗口大小。

空间复杂度：使用vector ans，因此空间复杂度为$O(N)O(N)$。