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

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

例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度的时候，返回空

方法一：暴力求解

求解思路
对于滑动窗口求解最大值，直接遍历，然后求位于窗口中元素的最大值，然后记录即可。

图片说明

解题代码

class Solution {//参考牛客官方解答code
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> myret;
        if (num.size() == 0 || size < 1 || num.size() < size) return myret;
        //判断条件，当num的大小等于0或者滑动窗口的size小于1或者滑动窗口移动到数组最后面时
        //以上这些情况都会直接返回结果
        int n = num.size()
        for (int i = 0; i + size - 1 < n; ++i) {
            int j = i + size - 1;
            int max_val = num[j];
            for (int k = i; k < j; ++k) {
                max_val = max(max_val, num[k]);//在滑动窗口中进行判断最大值
            }
            myret.push_back(max_val);//保存最大值，循环完之后输出结果。
        }
        return myret;
    }
};

复杂度分析
时间复杂度：对数组进行一次遍历，并且滑动窗口的大小为输入参数，因此时间复杂度为O(N*WindowSize)
空间复杂度：没有引入额外的地址空间，因此为O(1)

方法二：优化思想，参考上海大学的我是工科小仙女的思路

求解思路
对于滑动窗口的移动，我们没有必要每一次都比较在滑动窗口内元素的大小，而是使用上一个滑动窗口中最大值元素和新进来元素的值来进行比较。（当然也可能会出现最大值出现在窗口的第一个位置，但是窗口的滑动造成上一个最大值的丢失，我们在代码中也进行了此情况的考虑）

图片说明

解题代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> myres=new ArrayList<>();
        if(num==null||size==0||num.length<size)return myres;
        //判断条件，当num的大小等于0或者滑动窗口的size小于1或者滑动窗口移动到数组最后面时
        //以上这些情况都会直接返回结果
        int tmp=0;
        int maxNum=num[0];
        for(int i=1;i<size;i++){//在滑动窗口中进行判断
            if(num[i]>maxNum){
                tmp=i;
                maxNum=num[i];
            }
        }
        myres.add(maxNum);
        int j=size;
        while(j<num.length){
            if(num[j]>=maxNum){//优化判断，当滑动窗口移动到下一个位置时进行相应判断
                maxNum=num[j];
                tmp=j;
            }else{
                if(j-size+1>tmp){
                    maxNum=num[j-size+1];
                    tmp=j-size+1;
                    for(int i=j-size+1;i<=j;i++){
                        if(num[i]>maxNum){
                              tmp=i;
                               maxNum=num[i];
                         }
                    }
                }
            }
            myres.add(maxNum);
            j++;
        }
        return myres;
    }
}

复杂度分析
时间复杂度：每次循环都是一层，时间复杂度为O(N)
空间复杂度：没有引入额外的地址空间，空间复杂度为O(1)