力扣239 滑动窗口最大值 「双端队列」

1、

用双端队列来做：队列的头在左侧 尾在右侧

也就是说最大的值在右边

nums[dq.front()] < i-k+1这句是去掉上一个窗口的多于元素<记住规律>假设滑动窗口大小为k队尾元素为i 队首i-k+1 比如3210-1 放进去第一个窗口还是321三个元素下一个窗口放0 0 < 3-3+1   210   1 <4-2

321 0 1-2    0 2-2

if(i >= k-1)是最后记录最大值的时候保证最开始的两个不被计算进来

2、

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