239. 滑動視窗最大值

1.題目描述

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

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

示例:

2.思路（雙向隊列）

使用雙向隊列max_index存儲下标。max_index有以下特點:

1.變量的最前端（也就是 max_index.front()）是此次周遊的最大值的下标

2.當我們遇到新的數時，将新的數和雙項隊列的末尾（也就是max_index.back()）比較，如果末尾比新數小，則把末尾扔掉，直到該隊列的末尾比新數大或者隊列為空的時候才停止，做法有點像使用棧進行括号比對。

3.雙項隊列中的所有值都要在視窗範圍内

特點一隻是友善我們擷取每次視窗滑動一格之後的最大值，我們可以直接通過 max_index.front() 獲得

通過特點二，可以保證隊列裡的元素是從頭到尾降序的，由于隊列裡隻有視窗内的數，是以他們其實就是視窗内第一大，第二大，第三大… 的數。

特點三，因為隻要視窗内第一大元素也就是這個 max_index.front() 在視窗内，那我們可以不用管第二大第三大元素在不在區間内了。因為答案一定是這個第一大元素。如果 max_index.front() 不在視窗内，則将其彈出，第二個大元素變成第一大元素，第三大元素變成第二大元素以此類推。

3.代碼

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        if(nums.empty()){
            return res;
        }
        deque<int> max_index;
        for(int i = 0;i < nums.size();++i){
            while(!max_index.empty() && nums[i] >= nums[max_index.back()]){//保證雙向隊列是遞減的
                max_index.pop_back();
            }
            max_index.push_back(i);
            if(max_index.front() == (i-k)){
                max_index.pop_front();
            }
            if(i >= k-1){
                res.push_back(nums[max_index.front()]);
            }
        }
        return res;
    }
};
           

4.複雜度分析

時間複雜度：O(n)，每個元素被處理兩次- 其索引被添加到雙向隊列中和被雙向隊列删除。

空間複雜度：O(n)，輸出數組使用了O(N−k+1) 空間，雙向隊列使用了O(k)。