239. 滑动窗口最大值

在这里插入图片描述

思路

当我们遍历数组时，我们需要维护一个双端队列，用于存储滑动窗口中的元素的索引。队列中的元素按照降序排列，即「队头元素是当前滑动窗口中的最大值」。
具体的步骤如下：
1. 创建一个双端队列 window，用于存储滑动窗口中的元素的索引。
2. 遍历整个数组，对于每个元素 nums[i]：
  - 如果「队列不为空」且「队头元素不在当前滑动窗口的范围内」，将队头元素从队列中删除，因为它已经不在滑动窗口中了。
  - 如果「队列不为空」且「当前元素 nums[i] 大于等于队尾元素所对应的数组元素 nums[window.back()] 」，将队尾元素从队列中删除，因为它不可能是滑动窗口中的最大值了。
  - 将当前元素的索引 i 加入队列的队尾。
  - 如果当前遍历的索引 i 大于等于滑动窗口的大小 k-1，说明当前滑动窗口已经形成，将队头元素所对应的数组元素 nums[window.front()] 加入结果数组 ans中。
    返回结果数组 ans。
通过以上的步骤，我们可以得到滑动窗口中的最大值。这是因为队列中的元素按照降序排列，所以队列的队头元素即为当前滑动窗口中的最大值。

代码

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> ans;int n = nums.size();deque<int> windows;for(int i=0; i<n; ++i){// 如果队列不为空且队头元素不在当前滑动窗口的范围内// 将队头元素从队列中删除if(!windows.empty() && windows.front() <= i-k){windows.pop_front();}// 如果队列不为空且当前元素大于队尾元素，删除队尾元素while(!windows.empty() && nums[windows.back()] <= nums[i]){windows.pop_back();}// 当前元素入队windows.push_back(i);// 如果当前遍历的索引大于等于滑动窗口的大小// 将队头元素所对应的数组元素加入结果数组中if(i >= k-1){ans.push_back(nums[windows.front()]);}}return ans;}
};