本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖
面試題59：滑動(dòng)窗口的最大值
題目要求：
給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，請找出所有滑動(dòng)窗口的最大值宾肺。例如，輸入數(shù)組{2,3,4,2,6,2,5,1}和數(shù)字3侵俗，那么一共存在6個(gè)滑動(dòng)窗口锨用，他們的最大值分別為{4,4,6,6,6,5}。
解題思路：
思路1：使用暴力求解隘谣。假設(shè)滑動(dòng)窗口長度為k增拥，每到一個(gè)點(diǎn)都向前遍歷k-1個(gè)節(jié)點(diǎn)，那么總時(shí)間復(fù)雜度為o(nk)。
思路2：長度為k的滑動(dòng)窗口其實(shí)可以看成一個(gè)隊(duì)列掌栅，而滑動(dòng)窗口的移動(dòng)可以看成隊(duì)列的出隊(duì)和入隊(duì)秩仆，因此本題可以轉(zhuǎn)化為求長度為k的隊(duì)列的最大值。借助之前做過的9.用兩個(gè)棧實(shí)現(xiàn)隊(duì)列和30.包含min函數(shù)的棧猾封，我們可以實(shí)現(xiàn)求隊(duì)列的最大值澄耍。
下面我們分析下時(shí)間與空間復(fù)雜度。用兩個(gè)棧實(shí)現(xiàn)長度為k的隊(duì)列的入隊(duì)時(shí)間復(fù)雜度o(1)晌缘，出隊(duì)時(shí)間復(fù)雜度o(k),空間復(fù)雜度為o(k)齐莲；包含最值函數(shù)的棧（最大深度為k）的時(shí)間復(fù)雜度為o(1),空間復(fù)雜度為o(k)。因此長度為k的隊(duì)列的一次出隊(duì)+入隊(duì)操作（即窗口前移一位）時(shí)間復(fù)雜度為o(k)枚钓，空間復(fù)雜度為o(k)。而這個(gè)窗口需要完成在長度為n的數(shù)組上從頭到尾的滑動(dòng)瑟押，因此搀捷，本解法的時(shí)間復(fù)雜度為o(nk)，空間復(fù)雜度o(k)多望。
思路3：把可能成為最大值數(shù)字的下標(biāo)放入雙端隊(duì)列deque嫩舟，從而減少遍歷次數(shù)。首先怀偷，所有在沒有查看后面數(shù)字的情況下家厌，任何一個(gè)節(jié)點(diǎn)都有可能成為某個(gè)狀態(tài)的滑動(dòng)窗口的最大值，因此椎工，數(shù)組中任何一個(gè)元素的下標(biāo)都會(huì)入隊(duì)饭于。關(guān)鍵在于出隊(duì)，以下兩種情況下维蒙，該下標(biāo)對應(yīng)的數(shù)字不會(huì)是窗口的最大值需要出隊(duì)：(1)該下標(biāo)已經(jīng)在窗口之外掰吕，比如窗口長度為3，下標(biāo)5入隊(duì)颅痊，那么最大值只可能在下標(biāo)3,4,5中出現(xiàn)殖熟，隊(duì)列中如果有下標(biāo)2則需要出隊(duì)；(2)后一個(gè)元素大于前面的元素斑响，那么前面的元素出對菱属，比如目前隊(duì)列中有下標(biāo)3、4舰罚，data[3] = 50,data[4]=40纽门，下標(biāo)5入隊(duì)，但data[5] = 70营罢，則隊(duì)列中的3膜毁，4都需要出隊(duì)。
數(shù)組{2,3,4,2,6,2,5,1}的長度為3的滑動(dòng)窗口最大值求解步驟如下
步驟 插入數(shù)字 滑動(dòng)窗口 隊(duì)列中的下標(biāo) 最大值
1 2 2 0(2) N/A
2 3 2,3 1(3) N/A
3 4 2,3,4 2(4) 4
4 2 3,4,2 2(4),3(2) 4
5 6 4,2,6 4(6) 6
6 2 2,6,2 4(6),5(2) 6
7 5 6,2,5 4(6),6(5) 6
8 1 2,5,1 6(5),7(1) 5
時(shí)間復(fù)雜度在o(n)~o(nk)之間，空間復(fù)雜度o(k)瘟滨。
思路3的代碼實(shí)現(xiàn)如下：
package chapter6;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/18
* Time : 17:58
* Description:滑動(dòng)窗口的最大值
**/
public class P288_MaxInSlidingWindow {
//把可能會(huì)成為最大值的下標(biāo)存儲(chǔ)下來候醒，從而降低掃描次數(shù)
public static int[] maxInWindows(int[] data,final int size){
if(data==null ||data.length==0||data.length<size)
return new int[0];
int[] result = new int[data.length-size+1];
Deque<Integer> deque = new ArrayDeque<>();
for(int i=0;i<size-1;i++){
while (!deque.isEmpty()&&data[i]>=data[deque.getLast()])
deque.removeLast();
deque.addLast(i);
}
for(int i=size-1;i<data.length;i++){
while (!deque.isEmpty()&&i-deque.getFirst()+1>size)
deque.removeFirst();
while (!deque.isEmpty()&&data[deque.getLast()]<=data[i])
deque.removeLast();
deque.addLast(i);
result[i-(size-1)] = data[deque.getFirst()];
}
return result;
}
public static void main(String[] args){
int[] data = new int[]{2,3,4,2,6,2,5,1};
int[] result = maxInWindows(data,3);
for(int i=0;i<result.length;i++){
System.out.print(result[i]);
System.out.print("\t");
}
}
}
運(yùn)行結(jié)果
4 4 6 6 6 5
