精選力扣500題 第69題 239. 滑動視窗最大值【c++/java詳細題解】

1、題目

給你一個整數陣列 nums，有一個大小為 k 的滑動視窗從陣列的最左側移動到陣列的最右側，你只可以看到在滑動視窗內的 k 個數字，滑動視窗每次只向右移動一位，

回傳滑動視窗中的最大值，

示例 1：

輸入：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

示例 2：

輸入：nums = [1], k = 1
輸出：[1]

示例 3：

輸入：nums = [1,-1], k = 1
輸出：[1,-1]

示例 4：

輸入：nums = [9,11], k = 2
輸出：[11]

示例 5：

輸入：nums = [4,-2], k = 2
輸出：[4]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

2、思路

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

首先，我們知道最直接的做法是模擬滑動視窗的程序，每向右滑動一次都遍歷一遍視窗內的數字找最大的輸出，這樣的復雜度是 O ( k n ) O(kn) O(kn)，考慮優化一下，視窗向右滑動的程序實際上就是將處于視窗的第一個數字洗掉，同時在視窗的末尾添加一個新的數字，這就可以用雙向佇列來模擬，每次把尾部的數字彈出，再把新的數字壓入到頭部，然后找佇列中最大的元素即可，

如何快速找出滑動視窗中的最大值？

我們可以在佇列中只保留那些可能成為視窗最大元素的數字，去掉那些不可能成為視窗中最大元素的數字，考慮這樣一個情況，如果佇列中進來一個較大的數字，那么佇列中比這個數更小的數字就不可能再成為視窗中最大的元素了，因為這個大的數字是后進來的，一定會比之前早進入視窗的小的數字要晚離開視窗，那么那些早進入且比較小的數字就“永無出頭之日”，所以就可以彈出佇列，

因此佇列中的元素就會成保持一個單調遞減的順序，這樣我們就維護了一個單調佇列，

單調佇列

單調佇列是一個普通的雙端佇列，即隊頭和隊尾都可以添加和彈出元素，單調佇列顧名思義，佇列中元素之間的關系具有單調性，此處的單調性分為單調遞增與單調遞減，

以單調遞減佇列為例：

(這里我們規定遞減是指從隊頭到隊尾是遞減序列）

解題程序如下：

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

• 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);   
            if( i - k + 1 >= 0) res[j++] = nums[queue.getFirst()];           
        }
        return res;
    }
}

原題鏈接： 239. 滑動視窗最大值