13.1

生成窗口最大值数组

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：

[4 3 5] 4 3 3 6 7 窗口中最大值为5
4 [3 5 4] 3 3 6 7 窗口中最大值为5
4 3 [5 4 3] 3 6 7 窗口中最大值为5
4 3 5 [4 3 3] 6 7 窗口中最大值为4
4 3 5 4 [3 3 6] 7 窗口中最大值为6
4 3 5 4 3 [3 6 7] 窗口中最大值为7

如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。
请实现一个函数，给定一个数组arr，窗口大小w。
返回一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的最大值。
以本题为例，结果应该返回[5,5,5,4,6,7]。

思路

普通解法就是对于每个大小为w窗口都遍历，找到最大值，一共遍历n-w+1次，时间复杂度为O(w*n)
O(n)解法就是利用双端队列
双端队列中存放的是数组中的下标，表示的当前窗口中从大到小的最大值的下标
只需要遍历一次数组，对个数组中的每个值，如果比队列中末尾值小就放入队列，
否则就把队列中的最后一个值pop，直到可以放入为止。
然后更新结果res，队列中的第一个值是当前的最大值，但是要注意是否在窗口范围内，
如果不在，就pop，选择在窗口范围内的最大值

代码

public static int[] getMaxWindow(int[] arr, int w) {
	if (arr == null || w < 1 || arr.length < w) {
		return null;
	}
	int[] res = new int[arr.length - w + 1];
	//存放数组中数字的序号，且序号表示的数字顺序必须是从大到小
	LinkedList<Integer> qMax = new LinkedList<Integer>();
	//res的位置
	int index = 0;
	for(int i = 0; i < arr.length; i++){
		//添加元素
		//更新qmax的数据，对于满足顺序，即小于最后一个元素的直接放入，否则一直剔除最后一个，可能会使双端队列变空，直到满足要求
		while(!qMax.isEmpty() && arr[qMax.getLast()] <= arr[i]){
			qMax.removeLast();
		}
		qMax.add(i);
		//更新res
		if(i >= w - 1){
			//由于qmax是按照从小到大的顺序排列，因此最大值一定是第一个，但是可能出现一个数不在当前窗口的范围之中
			//检查qmax的数字是否有效，即在窗口之内
			while(qMax.getFirst() < index || qMax.getFirst() > index + w){
				qMax.removeFirst();
			}
			res[index++] = arr[qMax.getFirst()];
		}
		
	}
	return res;
	
}