力扣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; } };