239. Sliding Window Maximum 滑動視窗最大值

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Example: Input: nums = [1,3,-1,-3,5,3,6,7] , and k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [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 Note:  You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array. Follow up: Could you solve it in linear time?

給定一個數組 nums，有一個大小為 k 的滑動視窗從數組的最左側移動到數組的最右側。你隻可以看到在滑動視窗 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 ≤ 輸入數組的大小，且輸入數組不為空。 進階： 你能線上性時間複雜度内解決此題嗎？

思路：這道題給定了一個數組，還給了一個視窗大小k，讓我們每次向右滑動一個數字，每次傳回視窗内的數字的最大值，而且要求我們代碼的時間複雜度為O(n)。提示我們要用雙向隊列deque來解題，并提示我們視窗中隻留下有用的值，沒用的全移除掉。大概思路是用雙向隊列儲存數字的下标，周遊整個數組，如果此時隊列的首元素是i - k的話，表示此時視窗向右移了一步，則移除隊首元素。然後比較隊尾元素和将要進來的值，如果小的話就都移除，然後此時我們把隊首元素加入結果中即可，參見代碼如下：

具體分析過程如下（參考劍指offer）： 

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q;
        for(int i=0;i<nums.size();++i)
        {
            while(!q.empty() && nums[i]>=nums[q.back()])  //目前數組元素大于雙端隊列後面的元素
                q.pop_back();
            if(!q.empty() && q.front()<=i-k) q.pop_front();  //當視窗滑過最大值後，删掉最大值
            q.push_back(i);
            if(i>=k-1) res.push_back(nums[q.front()]);  //能夠構成一個視窗後将每個視窗最大值插入傳回值清單
        }
        return res;
    }
};