用一个双端队列存放元素下标,最大元素对应的下标存在队头,最小元素对应的下标存在队尾。
窗口每次向后滑动时:1.判断队头能否留在队列,条件是当前下标 - 队头下标 >= k
2.维护队列的单调性:如果要加入的元素比队尾元素大,删除队尾元素,直到队尾元素大于要加入元素
3.注意第一次把最大值加入结果集的条件:if (i >= k - 1)
class Solution {
public:
vector<int> maxInWindows(vector<int>& nums, int k) {
vector<int> res;
deque<int> q; //双端队列
for (int i = 0; i < nums.size(); i++) {
if (!q.empty() && i - q.front() >= k) // 判断队头是否还能留在队列
q.pop_front();
while (!q.empty() && nums[q.back()] < nums[i]) // 维护队列的单调性
q.pop_back();
q.push_back(i);
if (i >= k - 1) // 有第一个窗口的条件
res.push_back(nums[q.front()]);
}
return res;
}
};