from CodeTop, Leetcode, 239. 滑动窗口最大值。
单调队列,使队列内部单调递减,队列头就是窗口最大元素。
题意:
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
解读:
维护一个单调队列,需要是双端队列,遍历数组,队列存储元素下标。当且仅当队列为空或者队列尾下表元素大于当前元素的时候,下表可以从尾端入队列;否则,下标元素从尾端出队列,直到满足条件,新的下标尾端入队列。这样可以保证队列内下标对应的元素是单调降序排列的,于是窗口最大值就是队列头元素。
但是需要保证队列尾元素下标和头元素下标的长度差不得大于滑动窗口长度,只需要每一次加入新元素的时候,顺带判断一下 i - q.front()
是否 大于等于 k,是的话就 pop_front()
出头元素。
当 i >= k-1
,队列长度第一次达到滑动窗口长度,开始加入结果数组。
代码及注释:
vector<int> ans; // 存储结果
deque<int> q; // 双端队列作为单调队列的数据结构,存储数组元素下标
for (int i = 0; i < nums.size(); i++){
while(q.size() && nums[q.back()] < nums[i]) q.pop_back();
// 保证队列尾下标对应元素大于等于当前元素,否则就不是单调递减了
q.push_back(i);
if (i - q.front() >= k) q.pop_front();
if (i >= k-1) ans.push_back(nums[q.front()]);
}
return ans;