滑动窗口最大值-力扣

在做这道题时，首先想到的解法是使用队列来做，维护一个队列，每次保存滑动窗口大小的长度，并判断此时队列中的最大值，但这样做，在k的值较大时，出现了超时问题，代码如下：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        queue<int> que;
        for(int i = 0; i < nums.size(); i++){
            que.push(nums[i]);
            while(que.size() == k){
                int maxNum = que.front();
                que.pop();
                que.push(maxNum);
                for(int flag = 0; flag < k - 1; flag++){
                    int tmp = que.front();
                    maxNum = max(maxNum, tmp);
                    que.pop();
                    que.push(tmp);
                }
                result.push_back(maxNum);
                que.pop();
            }
        }
        return result;
    }
};

使用deque双端队列来完成这道题，首先遍历前k个元素，将最大值的下标加入到队列中，如果新加入的下标对应的值大于队列前面下标对应的值，将其移除。这样保持这个队列维护的下标，对应的值时由大到小单调的。
之后每新插一个元素进来，继续维护这个单调的队列，然后判断队列最前的下标，是否还在滑动窗口内，如果不在，则移除。代码如下：

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

            while(dq.front() <= i - k){
                dq.pop_front();
            }
            result.push_back(nums[dq.front()]);
        }
        return result;
    }
};