?LeetCode刷題實(shí)戰(zhàn)239：滑動(dòng)窗口最大值

示例 1：

輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
滑動(dòng)窗口的位置 最大值
--------------- -----
[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]

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        int n = nums.size();
        if(n<k) return result;
        deque<int> que;
        for(int i=0;i<k;++i){
            while(!que.empty() && nums[que.back()]<nums[i])
            {
                que.pop_back();
            }
            que.push_back(i);
        }
        result.push_back(nums[que.front()]);
 
        for(int i=k;i<n;++i){
            while(!que.empty() && nums[que.back()]<nums[i])
            {
                que.pop_back();
            }
            if(!que.empty() && i-que.front()>=k)
                que.pop_front();
            que.push_back(i);
            result.push_back(nums[que.front()]);
        }
        return result;
    }
};