前言
眾所周知，《劍指offer》是一本“好書”泼舱。
為什么這么說？
因為在技術(shù)面試中枷莉，它里面羅列的算法題在面試中出現(xiàn)的頻率是非常非常高的娇昙。
有多高，以我目前不多的面試來看依沮，在所有遇到的面試算法題中涯贞，出現(xiàn)原題的概率大概能有6成，如果把基于原題的變種題目算上危喉，那么這個出現(xiàn)概率能到達9成宋渔，10題中9題見過。
至于為什么給“好書”這兩個字打引號辜限，因為這本書成了面試官的必備皇拣，如果考生不會這本書上的題目，就很可能得到面試官負面的評價。這本書快要成為評判學生算法能力的唯一標準氧急，這使得考前突擊變成了一個慣例颗胡，反而讓投機倒把成了必要，并不一定能真正的考察考生的算法能力吩坝。
對于劍指offer題解這個系列毒姨，我的寫文章思路是，對于看了文章的讀者钉寝，能夠：
- 迅速了解該題常見解答思路（奇技淫巧不包括在內(nèi)弧呐，節(jié)省大家時間，實在有研究需求的人可以查閱其它資料）
- 思路盡量貼近原書（例如書中提到的面試官經(jīng)常會要求不改變原數(shù)組嵌纲，或者有空間限制等俘枫，盡量體現(xiàn)在代碼中，保證讀者可以不漏掉書中細節(jié)）
- 盡量精簡話語逮走，避免冗長解釋
- 給出代碼可運行鸠蚪，注釋齊全，對細節(jié)進行解釋
快速找到我的《劍指offer題解》專欄：
- 公眾號（Rude3Knife）：底部導(dǎo)航欄——劍指offer題解
- CSDN（@Rude3Knife）：劍指offer題解專欄
題目介紹
劍指offer面試題59題
給定一個數(shù)組和滑動窗口的大小师溅，找出所有滑動窗口里數(shù)值的最大值茅信。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3险胰，那么一共存在6個滑動窗口汹押，他們的最大值分別為{4,4,6,6,6,5}矿筝； 針對數(shù)組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[2,3,4],2,6,2,5,1}起便， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}窖维， {2,3,4,[2,6,2],5,1}榆综， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}铸史。
解題思路
蠻力法
思路
掃描窗口k鼻疮，得到最大值。對于長度為n的數(shù)組琳轿，算法時間復(fù)雜度O（nk）
顯然不是最優(yōu)解判沟。
用兩個棧實現(xiàn)隊列
思路
面試題30中，我們實現(xiàn)過用兩個棧實現(xiàn)了隊列崭篡，可以在O（1）時間得到棧的最大值挪哄，也就可以得到隊列的最大值。
這樣總的時間復(fù)雜度O（n）
但是這樣的思路寫代碼琉闪，等于同時要寫兩個題目迹炼，面試時間可能不允許。
雙端隊列
思路
參考解釋：
https://cuijiahua.com/blog/2018/02/basis_64.html
數(shù)組的第一個數(shù)字是2，把它存入隊列中斯入。第二個數(shù)字是3砂碉，比2大，所以2不可能是滑動窗口中的最大值刻两，因此把2從隊列里刪除增蹭，再把3存入隊列中。第三個數(shù)字是4磅摹，比3大沪铭，同樣的刪3存4。此時滑動窗口中已經(jīng)有3個數(shù)字偏瓤，而它的最大值4位于隊列的頭部杀怠。
第四個數(shù)字2比4小，但是當4滑出之后它還是有可能成為最大值的厅克，所以我們把2存入隊列的尾部赔退。下一個數(shù)字是6，比4和2都大证舟，刪4和2硕旗，存6。就這樣依次進行女责，最大值永遠位于隊列的頭部漆枚。
但是我們怎樣判斷滑動窗口是否包括一個數(shù)字？應(yīng)該在隊列里存入數(shù)字在數(shù)組里的下標抵知，而不是數(shù)值墙基。當一個數(shù)字的下標與當前處理的數(shù)字的下標之差大于或者相等于滑動窗口大小時，這個數(shù)字已經(jīng)從窗口中滑出刷喜，可以從隊列頭部把它刪除残制。因此，我們既有可能從頭部刪除數(shù)字掖疮，又可能從尾部刪除數(shù)字初茶，所以要雙端隊列。
代碼
注意點：
ArrayDeque的幾個API：pollFirst浊闪、peekFirst等
ArrayDeque保存的是下標
最新的數(shù)的下標是必定加進去的恼布。
import java.util.ArrayList;
import java.util.ArrayDeque;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> result = new ArrayList<>();
// 排除特殊情況，窗口的長度為0
if (size==0) return result;
// 滑動窗口最左邊數(shù)的index
int begin;
// 建立一個雙端隊列
ArrayDeque<Integer> q = new ArrayDeque<>();
for(int i=0;i<num.length;i++){
// begin是窗口起始位置
begin = i-size+1;
// 隊列空搁宾，直接加入
if(q.isEmpty())
q.add(i);
// 若隊列最左邊值已經(jīng)不在窗口內(nèi)折汞，直接刪除
else if(begin > q.peekFirst())
q.pollFirst();
// 從隊尾開始比較，把所有比他小的值丟掉
while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
q.pollLast();
// 隨后再把它放進去
q.add(i);
// 若窗口起始位置在數(shù)組的0位置上或者之后（窗口是完整大小的）猛铅，才計算窗口的有效最大值
if(begin>=0){
// 永遠是隊列最左邊最大字支，加入結(jié)果集
result.add(num[q.peekFirst()]);
}
}
return result;
}
}
總結(jié)
采用雙端隊列，非常巧妙地一題。
