==双端队列结构实质上指的是：如果此时形成的窗口状况，不想让R往右动了，而让L往右动。谁会以此成为最大值的优先级。为什么弹出的数不再找回，原因是在窗口滑动的过程中，被弹出的数的优先级已经被后来的大数取代了，这就是尾端加入，前一个数比当前数小则弹出，比当前数大就加入当前数的道理==

假设一个固定大小为W的窗口，以此划过arr，返回每一次划出状况的最大值

package class01;

import java.util.LinkedList;

public class Code01_SlidingWindowMaxArray {

public static int[] getMaxWindow(int[] arr, int w) {

if (arr == null || w < 1 || arr.length < w) {

return null;

}

// Java中LinkedList就是双端队列，双向链表

// 其中放的是下标位置，头代表 （大->小）尾

LinkedList<Integer> qmax = new LinkedList<Integer>();

// 窗口在滑动的过程中，最终会生成arr长度-窗口起始宽度+1个值

int[] res = new int[arr.length - w + 1];

int index = 0;

// L...R

// R

for (int R = 0; R < arr.length; R++) { // 当前让 i -> [i] 进窗口 ， i 就是 r

// R 位置的值 可以放在比他大的数后，或者空

// 双端队列不为空，且双端队列尾部的值小于当前要进入窗口的值

while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {

// 双端队列从尾部弹出

qmax.pollLast();

}

// 经过上述的while，最终把当前进入窗口的数放入双端队列的尾部

qmax.addLast(R);

// 数进来了

// 如果窗口没有形成W的长度之前，不弹出数字的

// 当前下标是R, R-W就是需要过期的下标。

// 如果双端队列的头部保存的下标等于R-W，就头部弹出。实质R-W就是我们原始结构的L下标

if (qmax.peekFirst() == R - w) {

qmax.pollFirst();

}

// 以上窗口更新做完了

// 窗口没有形成W长度之前，不收集答案。形成W长度后，每一次收集一个答案

if (R >= w - 1) {

res[index++] = arr[qmax.peekFirst()];

}

}

return res;

// for test

public static int[] rightWay(int[] arr, int w) {

if (arr == null || w < 1 || arr.length < w) {

return null;

}

int[] res = new int[arr.length - w + 1];

int index = 0;

int L = 0;

int R = w - 1;

while (R < arr.length) {

int max = arr[L];

for (int i = L + 1; i <= R; i++) {

max = Math.max(max, arr[i]);

res[index++] = max;

L++;

R++;

return res;

}

// for test

public static int[] generateRandomArray(int maxSize, int maxValue) {

int[] arr = new int[(int) ((maxSize + 1) * Math.random())];

for (int i = 0; i < arr.length; i++) {

arr[i] = (int) (Math.random() * (maxValue + 1));

return arr;

}

// for test

public static boolean isEqual(int[] arr1, int[] arr2) {

if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {

return false;

}

if (arr1 == null && arr2 == null) {

return true;

}

if (arr1.length != arr2.length) {

return false;

}

for (int i = 0; i < arr1.length; i++) {

if (arr1[i] != arr2[i]) {

return false;

}

return true;

public static void main(String[] args) {

int testTime = 100000;

int maxSize = 100;

int maxValue = 100;

System.out.println("test begin");

for (int i = 0; i < testTime; i++) {

int[] arr = generateRandomArray(maxSize, maxValue);

int w = (int) (Math.random() * (arr.length + 1));

int[] ans1 = getMaxWindow(arr, w);

int[] ans2 = rightWay(arr, w);

if (!isEqual(ans1, ans2)) {

System.out.println("Oops!");

}

}

System.out.println("test finish");

}