滑动窗口的最大值

问题描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。

思路分析

我的想法是先设置一个变量k用来记录每个滑动窗口的起始位置，如第一个滑动窗口k=0；然后取出数组中相应滑动窗口大小的数组的最大值，目前用选择排序思想取出每个滑动窗口最大值，如第一个[2,3,4]最大值为4，然后通过循环条件k与size，当k+size大于数组长度，也就是遍历完所有滑动窗口，每次都将每个窗口最大值保存起来即可

码上有戏

import java.util.ArrayList;
public class Solution {
   public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> array=new ArrayList<Integer>();
        if(num==null||size<=0)return array;
        int len=num.length;
        int k=0;
       while(k+size<=len){
          array.add(maxInWindow(num,k,size));
          k++;
       }
   return array;
        
    }
    
    private int maxInWindow(int[] num,int k,int size){
        int i=k;
        int top=num[k];
        for(;i<k+size;i++){
            if(num[i]>top)
                top=num[i];
        }
            return top;
    }
}