LeetCode：239 滑動視窗最大值 雙端隊列 O(n)

給定一個數組 nums，有一個大小為 k 的滑動視窗從數組的最左側移動到數組的最右側。你隻可以看到在滑動視窗内的 k 個數字。滑動視窗每次隻向右移動一位。

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

示例:

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

輸出: [3,3,5,5,6,7]

解釋:

提示：

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

進階：

你能線上性時間複雜度内解決此題嗎？

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/sliding-window-maximum

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

思路

使用雙端隊列存儲一個滑動視窗内的元素下标，這個雙端隊列必須滿足以下幾個特征：

• 隊頭元素是滑動視窗内最大元素的下标
• 從隊頭到隊尾的下标對應的元素必須遞減
• 存儲的下标必須在滑動視窗内

維護性質2

不斷枚舉滑動視窗的右端點

r

，如果

nums[r]

比隊尾元素對應的數

nums[back()]

大，那麼不斷彈出隊尾元素，直到隊尾大于

nums[r]

（因為比新數

nums[r]

小的數，都不能作為區間的最大元素了，可以舍棄），新元素入隊尾

維護性質3

因為右端點推進了，左端點

l

也要推進，還要檢查目前區間的最大值（隊頭存儲的下标）是否已經超過了目前的視窗，如果是，那麼隊頭要彈出

儲存下标是為了快速判斷存儲的元素是否超過滑動視窗的範圍，而元素遞減保證了最大元素超出區間時被彈出，隊頭仍然是最大元素

代碼

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        vector<int> ans;
        if(k==0) return ans;
        if(k==1) return nums;
        deque<int> q;
        // 初始化隊列
        for(int i=0; i<k; i++) 
        {
            while(!q.empty() && nums[i]>nums[q.back()]) 
                q.pop_back();
            q.push_back(i);
        }
        ans.push_back(nums[q.front()]);
        // 開始滑動，彈出超出區間或小的元素，進來新元素
        // l+k-1：區間右端點下标
        for(int l=1; l+k-1<nums.size(); l++)
        {
            if(l-1==q.front()) q.pop_front();
            while(!q.empty() && nums[l+k-1]>nums[q.back()]) 
                q.pop_back();
            q.push_back(l+k-1);
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};