滑动窗口

滑动窗口的基本思想

之前学习过双指针,有快慢指针和碰撞指针,其实有点类似滑动窗口,其实滑动窗口就是双指针的一种特殊类型

简单来说,滑动窗口就像是一个不断移动的连续区间,看下图

image-20240409155112853

假如窗口的大小是3,当不断有新数据来时,我们会维护一个大小为3的一个区间,超过3的就将新的放入老的移走。

这个过程有点像火车在铁轨上跑,原始数据可能保存在一个很大的空间里(铁轨),但是我们标记的小区间就像一列长度固定的火车,一直向前走。

  • 窗口:窗口其实就是两个变量left和right之间的元素,也可以理解为一个区间。
    • 窗口大小可能固定,也可能变化,如果是固定大小的,那么自然要先确定窗口是否越界,再执行逻辑处理。
    • 如果不是固定的,就要先判断是否满足要求,再执行逻辑处理。
  • 滑动:说明这个窗口是移动的,事实上移动的仍然是left和right两个变量,而不是序列中的元素。当变量移动的时,其中间的元素必然会发生变化,因此就有了这种不断滑动的效果。

这里,我们根据两种窗口的情况,可以想到以下题目:

  • 如果是固定的,则一般会让你求哪个窗口的元素最大、最小、平均值、和最大、和最小等等类型的问题。
  • 如果窗口是变的,则一般会让你求一个序列里最大、最小窗口是什么等等。

滑动窗口题目本身没有太高的思维含量,但是实际在解题的时候仍然会感觉比较吃力,主要原因有以下几点:

  • 解题最终要落实到数组上,特别是边界处理上,这是容易晕的地方,稍有疏忽就难以得到准确的结果。
  • 有些元素的比较、判断等比较麻烦,不仅要借助集合等工具,而且处理过程中还有一些技巧,如果不熟悉会导致解题难度非常大。
  • 堆!我们在前面介绍过,堆结构非常适合在流数据中找固定区间内的最大、最小等问题。因此滑动窗口经常和堆一起使用可以完美解决很多复杂的问题。

问:双指针和滑动窗口啥区别呢?

滑动窗口是双指针的一种类型,主要关注两个指针之间元素的情况,因此范围更小一些,而双指针的应用范围更大,花样也更多。

两道入门题

L643 子数组最大平均数

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k

请你找出平均数最大且 长度为 k 的连续子数组,并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1:

输入:nums = [1,12,-5,-6,50,3], k = 4
输出:12.75
解释:最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2:

输入:nums = [5], k = 1
输出:5.00000

提示:

  • n == nums.length
  • 1 <= k <= n <= 105
  • -104 <= nums[i] <= 104

拿到这道题第一个思路有两点会绕远路:

  • 第一想法可能是每一次将窗口内再一次循环算出来就行,但是这样数据多的时候,严重超时,所以正确算法是应该直接算出窗口的值,只需要将移动的窗口新值在原来的窗口总和sum基础上算就行
  • 第二个想法可能是:窗口应该有左右两个指针,但是这样缺点是多一个变量,还不如直接用right右指针right-k算出左指针

这道题整体思路是,算出sum后,然后窗口初始位置+1,开始

最终答案

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        //固定窗口,当k>数组长度或者数组为0直接返回
        if (k> nums.length || nums.length <1 || k <1) {
            return 0;
        }
        int sum =0;
        for (int i = 0; i < k; i++) {
            sum+=nums[i];
        }
        //如果k和数组长度相同,直接算平均值即可
        if (nums.length==k)return (double) sum /k;
        int right = k;
        int res =sum;
        while (right< nums.length) {
            sum+=nums[right]-nums[right-k];
            res = Math.max(res, sum);
            right++;

        }
        return (double) res/k;


    }
}

L674 最长连续递增序列

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

连续递增的子序列 可以由两个下标 lrl < 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

过程整个其实很简单,就是right不断走,走一个判断与前一个相比是否比前一个大,如果大就继续走,否则,左指针就到右指针的位置

这个时候你可能会想到,左指针直接到右指针,怎么计算区间长度?

很简单,走一次减一次就行

假设有1,3,5,7,3,2,5,6,9,有大致下列过程:

  1. 当right和left都为0的时候,if条件为false,right++
  2. 一直到right==3时,此时res求出得4,继续到新一轮循环,这时候if为true,left =4;
  3. 此时已经得到结果
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int left = 0, right = 0;
        int res = 0;
        while (right < nums.length) {
            if (right > 0 && nums[right] <= nums[right - 1]) {
                left = right;
            }
            right++;
            res = Math.max(res, right - left);
        }
        return res;
    }
}