网站找什么公司做,ppt免费下载雷锋网站,建设银行app忘记登录密码,经典 wordpress主题下载窗口#xff1a;窗口其实就是两个变量left和ight之间的元素#xff0c;也可以理解为一个区间。窗口大小可能固定#xff0c;也可能变化。滑动#xff1a;窗口是移动的#xff0c;事实上移动的仍然是left和ight两个变量#xff0c;而不是序列中的元素。当变量移动的时窗口其实就是两个变量left和ight之间的元素也可以理解为一个区间。窗口大小可能固定也可能变化。滑动窗口是移动的事实上移动的仍然是left和ight两个变量而不是序列中的元素。当变量移动的时其中间的元素会发生变化。
滑动窗口题目本身没有太高的思维含量但是实际在解题的时候仍然会感觉比较吃力主要原因有以下几点
解题最终要落实到数组上特别是边界处理上这是容易晕的地方稍有疏忽就难以得到准确的结果。有些元素的比较、判断等比较麻烦不仅要借助集合等工具而且处理过程中还有一些技巧如果不熟悉会导致解题难度非常大。堆堆结构非常适合在流数据中找固定区间内的最大、最小等问题。因此滑动窗口经常和堆一起使用可以完美解决很多复杂的问题。
最后一个问题那双指针和滑动窗口有啥区别滑动窗口是双指针的一种类型主要关注两个指针之间元素的情况因此范围更小一些而双指针的应用范围更大花样也更多。
子数组最大平均数
643. 子数组最大平均数 I - 力扣LeetCode
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组并输出该最大平均数。
任何误差小于 10^-5 的答案都将被视为正确答案。
示例 1
输入nums [1,12,-5,-6,50,3], k 4
输出12.75
解释最大平均数 (12-5-650)/4 51/4 12.75示例 2
输入nums [5], k 1
输出5.00000提示
n nums.length1 k n 105-104 nums[i] 104
大小固定的滑动窗口
public double findMaxAverage(int[] nums, int k)
{//计算前k个的和int windowSum 0;for(int i 0; i k; i)windowSum nums[i];int ans windowSum;//滑动窗口,右边加上一个则左边就减掉一个for (int i k; i nums.length; i){windowSum windowSum nums[i] - nums[i - k];ans Math.max(ans, windowSum);}//返回平均值return (double) ans / k;
}最长连续递增序列
674. 最长连续递增序列 - 力扣LeetCode
给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1
输入nums [1,3,5,4,7]
输出3
解释最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的因为 5 和 7 在原数组里被 4 隔开。 示例 2
输入nums [2,2,2,2,2]
输出1
解释最长连续递增序列是 [2], 长度为1。提示
1 nums.length 104-109 nums[i] 109
大小可变的滑动窗口
实现方式一
public int findLengthOfLCIS(int[] nums)
{int left 0;int right 0;int ans 0;while (right nums.length){//若窗口右侧不满足严格递增条件则left跳到right的位置重新开始计算if(right 0 nums[right] nums[right - 1])left right;//无论是否满足条件right都先向右移动right;ans Math.max(ans, right - left); //维护最大的窗口大小}return ans;
}实现方式二
public int findLengthOfLCIS(int[] nums)
{int left 0;int ans 1; //nums至少有一个元素所以最长连续递增的子序列至少为1for(int right 1; right nums.length; right){//若窗口右侧不满足严格递增条件则left跳到right的位置重新开始计算if(nums[right] nums[right - 1])left right;ans Math.max(ans, right - left 1); //维护最大的窗口大小}return ans;
}
