滑動窗口題目
由一個代表題目缚柳，引出一種結(jié)構(gòu)
【題目】
有一個整型數(shù)組arr和一個大小為w的窗口從數(shù)組的最左邊滑到最右邊埃脏，窗口每次 向右邊滑一個位置。
例如秋忙，數(shù)組為[4,3,5,4,3,3,6,7]彩掐，窗口大小為3時:
[4 3 5]4 3 3 6 7
4[3 5 4]3 3 6 7
4 3[5 4 3]3 6 7
4 3 5[4 3 3]6 7
4 3 5 4[3 3 6]7
4 3 5 4 3[3 6 7]
窗口中最大值為5 窗口中最大值為5 窗口中最大值為5 窗口中最大值為4 窗口中最大值為6 窗口中最大值為7
如果數(shù)組長度為n，窗口大小為w灰追，則一共產(chǎn)生n-w+1個窗口的最大值堵幽。
請實現(xiàn)一個函數(shù)。 輸入:整型數(shù)組arr弹澎，窗口大小為w朴下。
輸出:一個長度為n-w+1的數(shù)組res，res[i]表示每一種窗口狀態(tài)下的 以本題為例苦蒿，結(jié)果應(yīng)該返回{5,5,5,4,6,7}殴胧。
第一步，實現(xiàn)以下要求：
要求：
- 窗口只能右邊界或左邊界向右滑的情況下，維持窗口內(nèi)部最大值或者最小值快速更新的結(jié)構(gòu)
- 窗口內(nèi)最大值與最小值更新結(jié)構(gòu)的原理與實現(xiàn)
用戶可以隨意地控制左邊界或右邊界的移動团滥，但是竿屹，左邊界不能超過右邊界，求每次窗口內(nèi)的最大值
思路：
- 使用雙端隊列灸姊，存儲在窗口內(nèi)的數(shù)據(jù)的index拱燃，并保證雙端隊列內(nèi)保存的index的排列順序是按照數(shù)據(jù)從大到小順序（嚴(yán)格從大到小）排列的力惯。（雙端隊列的左右兩端既可以加數(shù)據(jù)碗誉，也可以減數(shù)據(jù)）
- 當(dāng)右邊界向右滑時，將加入的數(shù)據(jù)從雙端隊列的右端加進去父晶，如果將數(shù)據(jù)放在最右邊诗充，可以在雙端隊列中使得數(shù)據(jù)保持從大到小的排序，則將index存入（即該數(shù)據(jù)比雙端隊列中最小的數(shù)還杏战ā）；如果該數(shù)據(jù)比雙端隊列中最右邊的數(shù)據(jù)大碟绑，則依次從右邊移出雙端隊列中的數(shù)據(jù)俺猿，直到該數(shù)據(jù)可以加進去為止。
- 當(dāng)左邊界向右滑時格仲，判斷雙端隊列中最大的數(shù)據(jù)是否是非法數(shù)據(jù)押袍，如果是，將最大的數(shù)據(jù)從雙端隊列的左邊移出凯肋，否則谊惭，不做任何操作。
- 雙端隊列中存儲的index是從小到大排列的侮东。
- 實際上圈盔，雙端隊列中維持的是，如果目前的窗口的右邊界不動了悄雅，讓左邊界依次往右移動驱敲，做窗口內(nèi)最大值的優(yōu)先級。
- 估計時間復(fù)雜度宽闲，每個位置的數(shù)字众眨，最多進窗口一次，最多出窗口一次容诬。所以雙端隊列更新的總代價是O（N）娩梨，所以單次獲得窗口最大值的平均代價是O（1）。
第二步览徒，解本道題
- 雙端隊列的右邊界移動三次狈定，然后求最大值
- 雙端隊列的右邊界移動一次，左邊界移動一次习蓬，求最大值
- 重復(fù)步驟二掸冤，直到右邊界到數(shù)組的最后一位厘托。
