【棧與隊列】移動視窗生成最大值的數組

功能需求

        有一個整數型數組arr和一個大小為w的視窗從數組的最左端滑到最右端，視窗每次向右滑動一個位置。就像是一個滑動的指針，從頭指向尾，然後輸出視窗中資料的最大值。

        例如，一組資料為arr[]  = [4，3，5，4，3，3，6，7]，視窗大小為w = 3時：

        [  4    3    5  ]  4    3    3    6    7                           視窗中最大值為 5

          4  [  3    5    4  ]  3    3    6    7                           視窗中最大值為 5  

          4    3  [  5    4    3  ]  3    6    7                           視窗中最大值為 5

          4    3    5  [  4    3    3  ]  6    7                           視窗中最大值為 5

          4    3    5    4  [  3    3    6  ]  7                           視窗中最大值為 5

          4    3    5    4    3  [  3    6    7  ]                         視窗中最大值為 5

        如果數組的長度為n，視窗大小為w，這一共産生n-w-7個視窗的最大值。

    要求：請實作一個函數。

        輸入：整型數組arr，視窗大小為w

        輸出：一個長度為n-w-1的輸入res，res[ i ]表達每一種視窗狀态下的最大值。{5,5,5,4,6,7}.

詳細解析

        如果資料長度為N，視窗大小為w，如果做出時間複雜度O(N*w)的解法是不能讓面試官滿意的，本題要求面試者想出的時間複雜度O(N)的實作。是以本題的關鍵在于利用雙端隊列來實作視窗最大值的更新。首先生成的是雙端隊列qmax，qmax中存放着數組arr中的下标。

    假設：周遊到arr[i]，qmax的放入規則為：

    1、如果qmax為空，直接把下标i放入qmax，放入過程結束。

    2、如果qmax不為空，取出目前qmax隊尾放入隊尾存放的下标，假設為j。

        1)如果arr[j] > arr[i]，直接把下标i放入qmax的隊尾，放入過程結束。

        2)如果arr[j] < arr[i]，把j從qmax中彈出，繼續qmax的放入規則。

    假設周遊到arr[i]，qmax的彈出規則為：

        如果qmax隊頭的下标等于i-w，說明目前qmax隊頭下标已經過期，彈出目前對頭下标即可。根據如上的放入的彈出規則，qmax便成了一個維護視窗為w的子數組的最大值更新的結構。舉例如下；

        1、開始時qmax為空，qmax={}

        2、周遊到arr[0] == 4，将下标0放入qmax，qmax= { 0 }。

        3、周遊到arr[1] == 3，目前qmax的隊尾下标為0，又有arr[0] > arr[1]，是以将下标1放入qmax尾部，qmax={ 0 ， 1}。

        4、周遊到arr[2] == 5，目前qmax的隊尾下标為1，又有arr[1] <= arr[2]，是以将下标1從qmax的尾部彈出，qmax變成{0}。目前qmax的隊尾下标為0，又有arr[0] <= arr[2]，是以将下标0從qmax尾部彈出，qmax變成{}。将下标2放入qmax，qmax={2}。此時已經周遊到下标2的位置，視窗arr[0,2]出現，目前qmax對頭的下标為2，是以視窗arr[0,2]的最大值為arr[2]（即為5）。

       5、周遊到arr[3]==4，目前qmax的隊尾下标為2，又有arr[2]>arr[3]，是以将下标了放入qmax尾部，qmax={2,3}。 視窗arr[1..3]出現，  目前qmax隊頭的下标為2，這個下标還沒有過期，是以視窗ar[1..3]的最大值為arr[2] (即5)。

        6、周遊到arr[4]== =3，目前qmax的隊尾下标為3，  又有arr[3]>arr[4]， 是以将下标4放入qmax尾部，qmax={2,3,4}。 視窗arr[2..4]出現，目前qmax隊頭的下标為2，這個下标還沒有過期，是以視窗arr[2..4]的最大值為arr[2] (即5)。

        7、周遊到arr[5]==3，目前qmax的隊尾下标為4,  又有arr[4]<= =arr[5]，是以将下标4從qmax的尾部彈出，qmax變為{2,3}。目前qmax的隊尾下标為了，又有arr[3]>arr[5]，是以将下标5放入qmax尾部，qmax= {2,3,5}。視窗arr[3..5]出現，目前qmax隊頭的下标為2,這個下标已經過期，是以從qmax的頭部彈出，  qmax變為{3,5}。目前qmax隊頭的下标為3，這個下标沒有過期，是以視窗arr[3..5]的最大值為arr[3] (即4)。

        8、周遊到arr[6]==6， 目前qmax的隊尾下标為5，又有arr[5]<=arr[6]， 是以将下标5從qmax的尾部彈出，qmax變為{3}。目前qmax的隊尾下标為3,  又有arr[3]<=arr[6]，是以将下标3從qmax的尾部彈出，qmax變為{}。将下标6放入qmax,qmax={6}。視窗ar([..]出現，目前qmax隊頭的下标為6，這個下标沒有過期，是以視窗arr[4..6]的 最大值為arr[6](即6)。

        9、 周遊到arr[7]==7， 目前qmax的隊尾下标為6，又有arr[6]<=arr[7], 是以将下标6 從qmax的尾部彈出，qmax 變為{}。将下标7放入qmax，qmax={7}。 視窗arr[5..7]出現，目前  qmax隊頭的下标為7，這個下标沒有過期，是以視窗arr[5..7]的最 大值為arr[7](即7)。

        10、依次出現的視窗最大值為[5,5,5,4,6,7]，在周遊過程中收集起來，最後傳回即可。

具體過程參看如下代碼中的getMax Window方法。

代碼實作

// 移動視窗擷取最大值方法
public int[] getMaxWindow(int[] arr,int w) {
	// 判斷數組資訊或者截取長度時候合格
	if (arr == null || w < 1 || arr.length < w) {
		// 傳回方法
		return;
	}
	// 執行個體化一個連結清單結構
	LinkedList<Integer> qmax = new LinkedList<Integer>();
	// 執行個體化一個int類型數組并且定義長度為執行的次數
	int[] res = new int[arr.length - w + 1];
	// 定義一個下标常量
	int index = 0;
	// 循環周遊數組
	for (int i = 0 ; i < arr.length ; i++) {
		// 判斷數組中時候還有資料，或者已經周遊到隊尾
		while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
			// 移除對頭元素
			qmax.pollLast();
		}
		// 隊尾添加最後一個元素
		qmax.addLast(i);
		// 判斷對頭元素時候為最後一個元素
		if (qmax.peekFirst() == i - w) {
			// 出隊第一個元素
			qmax.pollFirst();
		}
		// 如果移動到最後元素前
		if (i >= w - 1) {
			// 把得到的數組存入res集合中
			res[index++] = arr[qmax.peekFirst()];
		}
	}
	// 傳回資訊的集合
	return res;
}
           

總結分析

雙端隊列，将arr中的元素加入res該隊列中，若該隊列的隊尾元素小于等于要加入的元素，則不斷的彈出，直到隊尾元素大于該元素或者隊列為空。此時将該元素的序号加入隊列中。同時當 i-w == 隊頭的序号，則将隊頭元素彈出。上述過程中，  每個下标值最多進qmax-一次，  出qmax一-次。是以周遊的過程中進出雙端隊列的操作是時間複雜度為O(N)，整體的時間複雜度也為O(N)。寫完手工。。睡覺