劍指 Offer 59 - I. 滑動視窗的最大值 【c++/java詳細題解】

1、題目

給定一個陣列 nums 和滑動視窗的大小 k，請找出所有滑動視窗里的最大值，

示例:

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7] 
解釋: 

  滑動視窗的位置                最大值

-------------------------     -----

[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：

你可以假設 k 總是有效的，在輸入陣列不為空的情況下，1 ≤ k ≤ 輸入陣列的大小，

2、思路

(單調佇列) O ( n ) O(n) O(n)

給定一個陣列 nums 和滑動視窗的大小 k，讓我們找出所有滑動視窗里的最大值，

樣例：

如樣例所示，nums = [1,3,-1,-3,5,3,6,7]，k = 3，我們輸出[3,3,5,5,6,7]，

首先，我們可以想到最樸素的做法是模擬滑動視窗的程序，每向右滑動一次都遍歷一遍滑動視窗，找到最大的元素輸出，這樣的時間復雜度是 O ( n k ) O(nk) O(nk)，考慮優化，其實滑動視窗類似于資料結構雙端佇列，視窗向右滑動程序相當于向隊尾添加新的元素，同時再把隊首元素洗掉，

如何更快的找到佇列中的最大值？

其實我們可以發現，佇列中沒必要維護視窗中的所有元素，我們可以在佇列中只保留那些可能成為視窗中的最大元素，去掉那些不可能成為視窗中的最大元素，

考慮這樣一種情況，如果新進來的數字大于滑動視窗的末尾元素，那么末尾元素就不可能再成為視窗中最大的元素了，因為這個大的數字是后進來的，一定會比之前先進入視窗的小的數字要晚離開視窗，因此我們就可以將滑動視窗中比其小的數字彈出佇列，于是佇列中的元素就會維持從隊頭到隊尾單調遞減，這就是單調遞減佇列，

單調遞增佇列

對于佇列內的元素來說：

1. 在佇列內自己左邊的數就是陣列中左邊第一個比自己小的元素，
2. 當被彈出時，遇到的就是陣列中右邊第一個比自己小的元素 ，( 只要元素還在佇列中，就意味著暫時還沒有陣列中找到自己右側比自己小的元素)
3. 隊頭到隊尾單調遞增，隊首元素為佇列最小值，

單調遞減佇列

對于佇列內的元素來說：

1. 在佇列內自己左邊的數就是陣列中左邊第一個比自己大的元素，
2. 當被彈出時，遇到的就是陣列中右邊第一個比自己大的元素 ，只要元素還在佇列中，就意味著暫時還沒有陣列中找到自己右側比自己大的元素，
3. 隊頭到隊尾單調遞減，隊首元素為佇列最大值，

了解了單調佇列的一些性質以后，對于這道題我們就可以維護一個單調遞減佇列，來保存佇列中所有遞減的元素 ，隨著入隊和出隊操作實時更新佇列，這樣隊首元素始終就是佇列中的最大值，同時如果隊首元素在滑動視窗中，我們就可以將其加入答案陣列中，

實作細節：

為了方便判斷隊首元素與滑動視窗的位置關系，佇列中保存的是對應元素的下標，

具體解題程序如下：

初始時單調佇列為空，隨著對陣列的遍歷程序中，每次插入元素前，需要考察兩個事情：

• 1、合法性檢查：隊頭下標如果距離i 超過了 k ，則應該出隊，
• 2、單調性維護：如果 nums[i] 大于或等于隊尾元素下標所對應的值，則當前隊尾再也不可能充當某個滑動視窗的最大值了，故需要隊尾出隊，始終保持隊中元素從隊頭到隊尾單調遞減，
• 3、如次遍歷一遍陣列，隊頭就是每個滑動視窗的最大值所在下標，

時間復雜度分析： 每個元素最多入隊出隊一次，復雜度為 O ( n ) O(n) O(n)，

3、c++代碼

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int>q; //雙端佇列
        vector<int>res;
        for(int i = 0; i < nums.size(); i++){
            while(q.size() &&  i - k + 1 > q.front())  q.pop_front(); //判斷隊頭是否在滑動視窗范圍內
            while(q.size() && nums[i] >= nums[q.back()]) q.pop_back();//維護單調遞減佇列
            q.push_back(i); //將當前元素插入隊尾
            if(i >= k - 1)  res.push_back(nums[q.front()]); //滑動視窗的元素達到了k個，才可以將其加入答案陣列中
        }
        return res;
    }
};

4、java代碼

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> queue = new ArrayDeque<>(); //雙端佇列
        int[] res = new int[n - k + 1];
        for (int i = 0 , j = 0; i < n; i++) {
            //判斷隊頭是否在滑動視窗范圍內
            while (!queue.isEmpty() && i- k + 1 > queue.getFirst())   queue.pollFirst();
            //維護單調遞減佇列
            while (!queue.isEmpty() && nums[i] > nums[queue.getLast()])  queue.pollLast();
            queue.offer(i);    //將當前元素插入隊尾
            //滑動視窗的元素達到了k個，才可以將其加入答案陣列中
            if( i - k + 1 >= 0) res[j++] = nums[queue.getFirst()];           
        }
        return res;
    }
}

原題鏈接： 劍指 Offer 59 - I. 滑動視窗的最大值