滑动窗口的最大值

2018-05-13

编程练习

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

思路：读懂题目的话就应该很简单了，首先滑动窗口的size和数组的length之间的关系是length-size+1就是滑动窗口的个数。要注意一开始就能想到特殊情况：如滑动窗口的size为0或者大于数组长度时应该返回空的list。一般情况，如果符合的话就需要在每个滑动窗口里做排序，求得最大值。

　　这里可以借助ArrayList这个容器，构造滑动窗口可以用subList方法，注意使用该方法时的两个陷阱：

　　1.list.sublist(a,b)真正截取的区间是左闭右开的，即若a为0，b为1，此时只截取到了list.get(0)这一个数，但右边界可以溢出1，这是为了可以截取到最后一个数，即b可以取到list.size()这个值;

　　2.对截取到的子串做操作时，原始的list也会随之改变，为了不想让原始的list改变，需要采取new操作，例如：List hplist=new ArrayList(list.subList(a, b))。搞懂了上面全部，这道题就很简单了。
java代码如下：

import java.util.ArrayList;
import java.util.List;

public class MaxInWindows {
    public static ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> tmplist=new ArrayList<Integer>();
        if(size>num.length || size==0) {
        	return tmplist;
        }
    	for(int c:num) {
    		tmplist.add(c);
    	}
        ArrayList<Integer> reslist=new ArrayList<Integer>();
        for(int i=0;i<num.length-size+1;i++) {
        	//为了保证对hplist操作时，原始的tmplist不发生任何改变
        	List<Integer> hplist=new ArrayList<Integer>(tmplist.subList(i, i+size));
        	
        	hplist.sort(null);
        	int max=hplist.get(size-1);
        	reslist.add(max);
        }
    	return reslist;
    }
    public static void main(String[] args) {
		int [] arr= {2,3,4,2,6,2,5,1};
		System.out.println(maxInWindows(arr,3));
	}
}