作者:
链接:http://proprogrammar.com:443/article/861
声明:请尊重原作者的劳动,如需转载请注明出处
给定一个数组 nums
和滑动窗口的大小 k
,请找出所有滑动窗口里的最大值。
示例:
输入: 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
提示:
你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。
难度:简单;标签:队列,滑动窗口;编程语言:C++
class Solution {
public:
// 题解中的方法,看不大懂,先放这
// https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/cjie-jian-dian-zan-zui-gao-de-fang-fa-zhu-yao-zuo-/
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res; //用来存结果的vector
deque<int> tem;
for(int i=0; i<nums.size(); ++i)
{
while(!tem.empty() && nums[i]>nums[tem.back()])
{ //while这步操作是为了让当前窗口最大值的索引值放到tem的队头
tem.pop_back();
}
if(!tem.empty() && tem.front()<i-k+1) tem.pop_front();
//这里的if判断条件中的第二个是为了判断队头是否过期,也就是说队头的索引是否小于当前索引
//往左走k步,+1是因为索引是从0开始,若当前滑窗索引便把它清理掉。
tem.push_back(i);
if(i>=k-1) res.push_back(nums[tem.front()]);
}
return res;
}
};
这个可以参考leetcode 剑指 Offer 59 - II. 队列的最大值,滑动就是一端出队列,一端入队列,两题为I, II,很类似
都是deque保存递减可能最大值队列,这里与II不同的是只要一个depue,不需要queue了,所以是简单,II是中等(其它这题对不会做的来说还是难)
亲爱的读者:有时间可以点赞评论一下
全部评论