1. 判断当前队列的长度(当前值加进去后计算还是加入前计算)
2. 维护区间的最大值 -> 保证队头元素最大(hh)， 队列从头到尾单调递减， 如果当前队尾元素比当前元素小于等于，就弹出
维护区间的最小值 -> 保证队头元素最小(hh)， 队列从头到尾单调递增， 如果当前队尾元素比当前元素大于等于，就弹出
Leetcode 239
题目链接：https://leetcode.com/problems/sliding-window-maximum/
题目代码：
//solution1 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.size() && q.front() <= i - k) q.pop_front(); while(q.size() && nums[q.back()] <= nums[i]) q.pop_back(); q.push_back(i); if(i >= k - 1) res.push_back(nums[q.front()]); } return res; } }; //solution2 class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { const int N = 100010; vector<int> ans; int q[N]; int hh = 0, tt = -1; int n = nums.size(); for(int i = 0; i < n; i++) { while(hh <= tt && q[hh] <= i - k) hh++; while(hh <= tt && nums[q[tt]] <= nums[i]) tt--; q[++ tt] = i; if(i >= k - 1) ans.push_back(nums[q[hh]]); } return ans; } };
原文：https://www.cnblogs.com/realxjr/p/13709997.html