目标：介绍窗口以及窗口内最大值或最小值的更新结构（单调双向队列）
利用res[i]表示每一种窗口状态下的最大值。
import java.util.LinkedList; //滑动窗口 public class hello { public static int[] getMaxWindow(int[] arr,int w){ if(arr==null||w<1||arr.length<w){ return null; } //LinkedList表示双向链表，代表双端队列（双端队列只存下标不存值） LinkedList<Integer> qmax = new LinkedList<Integer>(); //res:结果数组 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); //队头的下标等于i-w,表明对头元素已过期 if(qmax.peekFirst()==i-w) { //队头元素弹出 qmax.pollFirst(); } //收集当前的最大值到res if(i>=w-1){ res[index++]=arr[qmax.peekFirst()]; } } //返回最大值数组 return res; } //打印 public static void printArray(int[] arr) { for (int i = 0; i != arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] arr = {4,3,5,4,3,3,6,7}; printArray(getMaxWindow(arr,3)); } }结果：5 5 5 4 6 7
注：
如果一个数组合格，则其子数组一定合格；如果一个数组不合格，则该数组往外扩都不合格。 import java.util.LinkedList; //滑动窗口 public class hello { public static int Window(int[] arr,int num){ if(arr==null||arr.length==0){ return 0; } //最小值双端队列（双端队列只存下标不存值） LinkedList<Integer> qmin = new LinkedList<Integer>(); //最大值双端队列 LinkedList<Integer> qmax = new LinkedList<Integer>(); int start=0; int end=0; int res=0; while(start<arr.length) { while(end<arr.length) { //最小值结构更新 while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[end]) { //队尾弹出 qmin.pollLast(); } //停止弹出，队尾添加元素 qmin.addLast(end); //最大值结构更新 while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[end]) { //队尾弹出 qmax.pollLast(); } //停止弹出，队尾添加元素 qmax.addLast(end); //不达标后停止循环 if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) { break; } end++; } //验证最小值是否过期 if(qmin.peekFirst()==start){ qmin.pollFirst(); } //验证最大值是否过期 if(qmax.peekFirst()==start){ qmax.pollFirst(); } res+=(end-start); start++; } return res; } public static void main(String[] args) { int[] arr = {4,3,5,4,3,3,6,7}; System.out.println(Window(arr,3)); } }结果：30
