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

这个题直接用滑动窗口每次找出窗口中的最大值是非常不理想的，必须做一些优化，我做的优化就是记住上次窗口的最大值和最大值所在的下表，下个窗口再决定要不要进行所有值比较大小。

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        if(size>num.length||num.length==0||size==0){
            return list;
        }
        int max = Integer.MIN_VALUE;
        int maxIndex = 0;
        for(int i = 0;i<size;i++){
            if(num[i]>max){
                max = num[i];
                maxIndex = i;
            }
        }
        list.add(max);
        int lastMax = max;
        int lastMaxIndex = maxIndex;
        for(int i = 1;i<num.length-size+1;i++){
            if(num[i+size-1]>=lastMax){
                list.add(num[i+size-1]);
                lastMaxIndex = i+size-1;
                lastMax = num[i+size-1];
            }else if(num[i+size-1]<lastMax&&lastMaxIndex>=i){
                list.add(lastMax);
            }else{//只有这个情况下才对窗口内所有值进行比较，否则可直接返回最大值
                int tempMax = Integer.MIN_VALUE;
                int tempIndex = Integer.MIN_VALUE;
                for(int j = i;j<i+size;j++){
                    if(num[j]>tempMax){
                        tempMax=num[j];
                        tempIndex = j;
                    }
                }
                list.add(tempMax);
                lastMax = tempMax;
                lastMaxIndex = tempIndex;
            }
        }
        return list;
    }
}