問題：
補充：
用一個雙端鏈表梢为，保證頭部一直是當前的最大值，雙端鏈表，左邊是頭部鼎天，右邊是尾部览妖，保證從頭部到尾部是嚴格降序的也就是頭部的數(shù)一定是最大的台诗。當鏈表不為空且加入的數(shù)比當前鏈表最后一個尾部的數(shù)大的時候如筛，彈出尾部躁锡，如果一直大就一直彈。然后加入當前數(shù)筒溃，當最頭部的數(shù)失效時，就是窗口向前移動沾乘，移出頭部下標時候怜奖，彈出來。如果還沒到當前窗口大小翅阵，就一直往里加數(shù)歪玲，如果到了窗口大小就開始向結果里加當前數(shù)的最大值迁央。
牛客初級課第八章滥崩。
首先岖圈，補充一下滑動窗口的基本思路，定義兩個變量l钙皮，r（l,r只能向右移動）蜂科，來標示一個窗口的大小，然后用一個雙端隊列（首部和尾部都能夠加或者彈出）來存儲短条，在原數(shù)組中的下標的位置导匣，具體過程如下
比如一組數(shù)組 2，5茸时，4贡定，6 ，起始時候l,r都是0可都，雙端隊列為空缓待，當r向右移動時，窗口大小為1渠牲，此時就是[2],5,4,6旋炒；此時雙端隊列里加入2的下標0；下一步r再向右移動一步嘱兼，此時窗口里是[2,5],4,6国葬；這時雙端隊列加入5的下標1，再加入一個比當前隊列里數(shù)大的數(shù)的時候芹壕，要先把原隊列里的數(shù)彈出汇四，然后再加當前數(shù)，比如原隊列里右2踢涌，要先把2彈出通孽，再加入5的下標，這一步執(zhí)行完后睁壁，雙端隊列里的值是1背苦；r再向右移動1位，此時數(shù)組是[2,5,4],6潘明，雙端隊列因為5>4行剂，所以4的下標直接加入到隊列里，雙端隊列里的數(shù)是 1钳降，2厚宰；此時如果l向左移動一步，數(shù)組編程了2，[5,4]铲觉，6澈蝙，這時看由于窗口移動而出窗口的2在雙端隊列里有沒有失效，因為雙端隊列里本來就不包含2的下標所以無影響撵幽，依次執(zhí)行下去即可灯荧。
這種方法是求窗口里的最大值，雙端隊列是頭大尾小盐杂，即從前到后遞減的雙端隊列逗载，如果求窗口最小值就相反。注意雙端隊列里存儲的數(shù)組的下標
以上就是處理滑動窗口的原理
思路：
利用滑動窗口的原理况褪，本題窗口大小已經(jīng)確定撕贞，即不存在l，r测垛，直接利用原理計算即可
代碼：
public static int[] getMaxWindow(int[] arr, int w) {
if (arr == null || w < 1 || arr.length < w) {
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++) {
//當隊列不是空且入隊列的數(shù)大于原隊列的最后一個數(shù)
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
qmax.pollLast();
}
qmax.addLast(i);
//當窗口向右移動捏膨，原來在窗口中的最左端數(shù)字失效了比如1234，w=3食侮，移動到了4号涯，3-3=0，所以下標為0的就失效锯七，退出隊列
if (qmax.peekFirst() == i - w) {
qmax.pollFirst();
}
//當i大于等于窗口大小時才開始計算窗口里的最大值
if (i >= w - 1) {
res[index++] = arr[qmax.peekFirst()];
}
}
return res;
}
// for test
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 };
int w = 3;
printArray(getMaxWindow(arr, w));
}
