Sliding window maximum

。題目假設

。重要問題

暴力法一下就想到，問題是要怎麼做才會使得複雜度降低

。直覺

第一個直覺是暴力法，對於每個 window 都去掃過一遍，但是複雜度會變為 O(k*n)

第二種方法是每個 window 都建 BST，複雜度是 O((n-k+1)*log k)

第三種方法是用 PriorityQueue，每次向右時把最左邊的元素刪掉，並加入新的元素，再去 peek 即可拿到最大值

。解決方法可行性

用 PriorityQueue 是最簡便可行的解

。解決方案

初始大小為 nums.length + 1 - k 的數組

從 i = 0 開始，每次向 PriorityQueue 裡面插入元素，當元素到達 k 個時，開始 peek 並加進結果

並且 peek 出一個值，加到結果裡

。資料結構

PriorityQueue

。複雜度

peek 是 O(log k)，要遍歷 n 個 => O(n log k)

。遇到的困難點、想錯的地方

不知道怎麼把「向右滑動 window 時把最左邊的元素刪掉」寫成程式碼

可以這樣想：如果 i > k-1 了，表示已經到達 window 上限，此時刪掉左邊的元素

這邊要想說 i 是 index，所以要跟 index 比較， k-1 才會是 index

i > k-1 表示當前的 index 是在 window 的右邊，這個狀況下，要刪掉 window 最左邊

window 最左邊的 index 要以 i - k 表示，也就是 index - gap

還有一個重點是我們只要看最大的，看完交給下一輪去刪除，所以要用 peek !!!!!

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] res = new int[nums.length-k+1];
    if (nums == null || nums.length < k || nums.length == 0) {
        return new int[0];
    }

    PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
    for (int i=0; i<nums.length; i++) {
        //delete leftest one if i > k-1
        if (i > k-1)
            pQ.remove(nums[i-k]);

        //everytime offer the right one
        pQ.offer(nums[i]);

        //poll the max if the window is full
        if (i >= k-1)
            res[i-k+1] = pQ.peek();
    }
    return res;
}

Follow up: 能否優化到 O(n) ?

Ans: 可以，要用雙向隊列做，

雙向隊列是可以在頭尾加入元素的一種 Queue，實作方法有 LinkedList, ArrayDeque

解題思路是：

我們在滑動窗口時，就把窗口左邊的元素丟掉，新進來的元素則跟 Deque 的後面元素比，

如果當前元素比 Deque 裡的大，那就刪掉 Deque 裡的東西，因為當前元素都比較大，

那麼 Deque 裡面就不可能有最大元素，

你會問說那要怎麼刪掉最左邊元素？如果存的是 value 的話，

答案是我們存的是 index

 public int[] maxSlidingWindow(int[] nums, int k) {
    int[] res = new int[nums.length-k+1];
    if (nums == null || nums.length < k || nums.length == 0) {
        return new int[0];
    }

    Deque<Integer> deque = new LinkedList<>();  //save index
    for (int i=0; i<nums.length; i++) {
        //delete element before current window
        while (!deque.isEmpty() && deque.peekFirst() + (k-1) < i)
            deque.pollFirst();

        //add element, and compare value
        while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            deque.removeLast();

        deque.addLast(i);

        if (i >= k-1)
            res[i-k+1] = nums[deque.peekFirst()];
    }
    return res;
}