滑动窗口的最值更新结构

导读

在看数组的时候，有个技巧是用双指针来构造滑动窗口，可是这个并没有记录着之间的最大值或者最小值。事实上这样记录滑动窗口的最值有时候还挺好用的。这里就是简单的介绍这么一种用法，用几道例题来说明下。顺便也是检验自己是不是熟练掌握了。

结构介绍

滑动窗口的最值更新结构其实就是一个双端队列，即可以从头部进头部出，也可以从尾部进尾部出。在遍历数组的时候，生成滑动窗口的过程中，这个双端队列的内容也就相应的从尾部装数填出来了。在里面放数组的下标，通过下标来获取原数组的值。这个队列的头部始终是这个滑动窗口的最值。
对于最大值更新结构：
如果下面那放的数字比该队列的尾部元素还要大或者是相等的话，就把尾部元素弹出来，原来尾部元素小弹出是因为这就是这个结构的定义，头部要放最大值，相等还要弹出是因为如果不弹出的话那么这个数字可能已经不在滑动窗口表示的范围里了，这样在计算涉及到长度的时候，队列里装的又是下标元素，可能就得不到我们想要的结果。
装完元素以后，还要看看头部元素是否还是在滑动窗口里，如果不在了还要弹出头部元素，因为我们要的是滑动窗口里的元素、最值。
对于最小值更新结构：
与最大值更新结构就是照葫芦画瓢，只是在判断的时候改下相应的逻辑就可以了。

例题1 ：生成窗口最大值数组

题目：

思路：

直接用滑动窗口的最大值更新结构，就出结果了。。。
具体的实现方案，或者说更新时怎么一回事，还是看代码就会清晰些。

代码：

	public static int[] getMaxWindow(int[] arr, int w) {
   	//w:窗口的大小
		if(arr == null || arr.length == 0 || w == 0) {
   
			return null;
		}
		
		// 最大值更新结构
		LinkedList<Integer> qmax = new LinkedList<Integer>();
		int[] res = new int[arr.length - w + 1];
		int index = 0;
		
		for(int i = 0; i < arr.length; i++) {
   
			// 如果下面的元素 比 队列的尾部元素 还要大于后者相等，就弹出
			while( !qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i] ) {
   
				qmax.pollLast();
			}
			qmax.addLast(i);
			
			if( qmax.peekFirst() < i-w+1 ) {
   	// 看看头部元素是不是还在滑动窗口的范围里。
				qmax.pollFirst();
			}
			
			if(i+1 >= w) {
   		// 达到窗口的大小就存储最大值
				res[index++] = arr[qmax.peekFirst()];
			}
		}
		
		return res; 
	}

例题2：最大值减去最小值小于等于num的子数组的数量

题目：

思路：

因为有最大最小值，可以考虑用滑动窗口的最值更新结构来存储。
对于一个数组来说，我们从头开始生成一个滑动窗口，并且记录这个滑动窗口的最值，在看看这个最大值减最小值是不是小于等于给定的num，如果是，就说明这个窗口还可以在往外扩；如果不是那么就可以计算这个滑动窗口的子数组的数量。
这里计算的时候先说一个小结论：
就是对于数组arr[i…j]，这个范围是满足题意的最大窗口数组范围，那个他的子数组的的最大值只可能比原来的小，最小值只可能比原来的大，所以这个范围的子数组都是符合题意的。
这样，我们只要扩到一定范围扩不下去了，就计算包含左边界的子数组，在把左边界的元素去掉，即滑动窗口缩小，这样有可能还可以再扩，在重复此步骤，直到遍历完数组即可。
同样，写的可能不清晰，看看代码应该会思路理顺一些。

代码：

	public static int getNum(int[] arr, int num) {
   
		if(arr == null || arr.length < 1) {
   
			return 0;
		}
		
		LinkedList<Integer> qmax = new LinkedList<Integer>();
		LinkedList<Integer> qmin = new LinkedList<Integer>();
		int res = 0;
		int i = 0;	// 滑动窗口左边界
		int j = 0;	// 滑动窗口右边界
		
		while(i < arr.length) {
   
			while(j < arr.length) {
   
				// 更新 最大值结构
				while( !qmax.isEmpty() &&  arr[qmax.peekLast()] <= arr[j]   ) {
   
					qmax.pollLast();
				}
				qmax.addLast(j);
				
				// 更新最小值结构
				while( !qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]  ) {
   
					qmin.pollLast();
				}
				qmin.addLast(j);
				
				// 看看是否 还能在往外扩
				if( arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num  ) {
   
					break;
				}
				
				j++;	//滑动窗口扩大
			}
			
			// 看更新结构的头部元素 还在不在滑动窗口的范围内
			if(qmax.peekFirst() == i) {
   
				qmax.pollFirst();
			}
			if(qmin.peekFirst() == i) {
   
				qmin.pollFirst();
			}
			 
			res += j-i; 	// 记录子数组的数量
			i++;  // 滑动窗口缩小
		}
		
		return res; 
	}