題目描述

給定一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口 k 內(nèi)的數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。
返回滑動(dòng)窗口最大值。
相關(guān)話題：?堆、Sliding Window????難度：?困難

示例

• 首先，最直觀的思路是遍歷數(shù)組，每k個(gè)數(shù)，遍歷k個(gè)數(shù)找到最大值，然后添加到結(jié)果數(shù)組中。時(shí)間復(fù)雜度

滑動(dòng)窗口：
為了滿(mǎn)足題目要求的線性時(shí)間復(fù)雜度，我們通過(guò)利用雙向鏈表設(shè)計(jì)一種遍歷規(guī)則。

• 首先定義一個(gè)雙向鏈表(滑動(dòng)窗口記錄數(shù)組的下標(biāo))，模擬滑動(dòng)窗口，窗口內(nèi)的元素從左到右的大小關(guān)系為大->小，數(shù)據(jù)會(huì)從窗口的右邊進(jìn)入
• 當(dāng)一個(gè)元素來(lái)臨，如果該元素大于或等于滑動(dòng)窗口的最右元素，則將最右元素彈出，依次直到最右元素大于該元素或滑動(dòng)窗口為空，然后將該元素壓入滑動(dòng)窗口
• 然后，檢查最左邊元素是否符合要求(是否過(guò)期)，如果過(guò)期，則將其彈出
• 將當(dāng)前窗口(已形成窗口)的最左元素(最大元素)添加到結(jié)果數(shù)組中

例子

假設(shè)給定數(shù)組，nums = [1,3,-1,-3,-5,3,6,7], 和 k = 3

• 遍歷數(shù)組，

  
  

如上圖，1來(lái)臨，此時(shí)滑動(dòng)窗口為空，直接壓入；3來(lái)臨，此時(shí)滑動(dòng)窗口最右端為0(對(duì)應(yīng)的值為1)，顯然3 > 1，那么將滑動(dòng)窗口最右端元素彈出，將3對(duì)應(yīng)的下標(biāo)1壓入；-3來(lái)臨，-3 < -1，直接壓入滑動(dòng)窗口。

• 當(dāng)當(dāng)前元素下標(biāo) - 滑動(dòng)窗口最左元素 == k，也就是最左元素過(guò)期了，它并不屬于當(dāng)前窗口的元素，則需要把它清除掉，例如-5來(lái)臨后，將它壓入到滑動(dòng)窗口，此時(shí)3顯然不屬于藍(lán)色窗口內(nèi)的元素，所以需要將其清除。
• 當(dāng)開(kāi)始形成窗口，也就是遍歷到數(shù)組下標(biāo)2，遍歷了k個(gè)元素，則開(kāi)始每遍歷一個(gè)元素，記錄窗口的最大值(最左元素)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0) return nums;
        LinkedList<Integer> window = new LinkedList<Integer>();
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        for(int i = 0;i < nums.length;i++){
            //彈出不符合規(guī)則的元素
            while(!window.isEmpty() && 
                  nums[i] >= nums[window.peekLast()]){
                window.pollLast();
            }
            window.addLast(i);
            //清除過(guò)期元素
            if(i - window.peekFirst() == k){
                window.pollFirst();
            }
            if(i >= k - 1){
               res[index++]  = nums[window.peekFirst()];
            }
        }
        return res;
    }
}