主要观点总结
本篇文章主要介绍了滑动窗口最大值的问题,给出了问题的描述以及三种不同编程语言的解决方案,分别是Java、C++和Python。
关键观点总结
关键观点1: 问题描述
给定一个整数数组和一个大小为k的滑动窗口,每次窗口向右移动一位,需要找到滑动窗口中的最大值。
关键观点2: 问题分析
可以将滑动窗口看作是一个单调队列,通过维护这个队列来找到最大值。在添加元素之前,需要移除比它小的元素,保证队列的单调性。队列中的最大值就是队头的元素。
关键观点3: 解决方案
使用双端队列来存储元素的下标,每次窗口移动时,移除队头元素如果它要离开窗口,然后添加当前元素的下标到队尾。在添加元素之前,移除队列中比它小的元素,保证队列中的最大值是队头元素。最后,当窗口长度大于等于k时,将队头元素加入到结果数组中。
文章预览
最近在网上看到一个帖子,4位阿里P7,35岁被裁后在杭州开了一家很有特点的包子铺,从位置,装修,产品到营销策划都精心设计,用互联网思维降维竞争普通包子铺,结果每月稳赔5万! --------------下面是今天的算法题-------------- 来看下今天的算法题,这题是LeetCode的第239题:滑动窗口最大值。 问题描述 来源: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
………………………………