问题
给定一个数组nums
和滑动窗口的大小k
,请找出所有滑动窗口里的最大值。
示例
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解答
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (nums.empty()) return {};
vector<int> res;
deque<int> d;
for (int i = 0; i < nums.size(); i++) { // i = k - 1时窗口创建完成
if (i >= k && nums[i - k] == d.front()) d.pop_front(); // 滑动后检查最大值是否还在队列中
while (!d.empty() && nums[i] > d.back()) d.pop_back(); // 维护队列的单调性
d.push_back(nums[i]);
if (i >= k - 1) res.push_back(d.front());
}
return res;
}
};
重点思路
单调队列模版题,必须掌握。