欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

201010剑指Offer学习总结:滑动窗口

程序员文章站 2023-12-26 23:09:21
...

20201010算法学习总结:滑动窗口

1. 什么是滑动窗口

滑动窗口就是在一个数组中用矩形框框起来的一个部分。在一些数组类题目中,我们可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到了右边,我们就可以从所有的候选结果中找到最优解。

对于这道题来说,数组就是正整数序列 [ 1, 2, 3, … , n ]。我们设滑动窗口的左边界为 i,右边界为 j,则滑动窗口框起来的是一个左闭右开区间 [i, j)。为了编程的方便,滑动窗口一般表示成一个左闭右开区间。

初始时,i=1, j=1,滑动窗口位于序列的最左侧,窗口大小为0。如下图所示的滑动窗口包含元素为2、3、4。

201010剑指Offer学习总结:滑动窗口

滑动窗口的重要性质是:窗口的左边界和右边界永远只能向右移动,不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n)。(如果左右边界向左移动的话应该叫做“回溯”,算法的时间复杂度就可能不止 O(n)了)

2. 例题一:和为s的连续正数序列

剑指 Offer 57 - II. 和为s的连续正数序列【难度:简单】

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

示例 1:

输入:target = 9
输出:[[2,3,4],[4,5]]

示例 2:

输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]

限制:

  • 1 <= target <= 10^5

思路:

在这道题中,我们关注的是滑动窗口中所有数的和。当滑动窗口的右边界向右移动时,也就是 j = j + 1,窗口中多了一个数字 j,窗口的和也就要加上 j。当滑动窗口的左边界向右移动时,也就是 i = i + 1,窗口中少了一个数字 i,窗口的和也就要减去 i。滑动窗口只有右边界向右移动(扩大窗口)和左边界向右移动(缩小窗口) 两个操作。

那么何时应该扩大或者缩小窗口呢?

  • 当窗口的和小于target 时,窗口的和需要增加,窗口右边界向右移动;
  • 当窗口的和大于target 时,窗口的和需要减少,窗口左边界向右移动;
  • 当窗口的和等于target 时,这时我们已经找到了一个可行解,记录下来窗口[i,j),接下来应该去找i+1开始的序列了。

代码:

public int[][] findContinuousSequence(int target) {
    int i = 1; // 滑动窗口的左边界
    int j = 1; // 滑动窗口的右边界
    int sum = 0; // 滑动窗口中数字的和
    List<int[]> res = new ArrayList<>();
    while (i <= target / 2) {
        if (sum < target) {
            // 右边界向右移动
            sum += j;
            j++;
        } else if (sum > target) {
            // 左边界向右移动
            sum -= i;
            i++;
        } else {
            // 记录结果
            int[] arr = new int[j-i];
            for (int k = i; k < j; k++) {
                arr[k-i] = k;
            }
            res.add(arr);
            // 左边界向右移动
            sum -= i;
            i++;
        }
    }
    return res.toArray(new int[res.size()][]);
}

3. 例题二:滑动窗口的最大值

剑指 Offer 59 - I. 滑动窗口的最大值【难度:简单】

给定一个数组 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

首先应该注意审题,本题是给定一个定长的数组,一个指定的窗口大小,求窗口在所有位置的窗口内元素最大值。最后返回的是一个数组,对应从左至右移动这个窗口时产生的每一个最大值。

另外,本题中 的滑动窗口是一个双闭区间。

  1. 一共会产生多少个不同位置的窗口?

    nums.length-k+1。所以返回的数组结果长度应为此值。

  2. 使用哪种数据结构来保存窗口的最值,使找出最值能实现O(1)复杂度?

    使用单调队列实现。我们只要保证deque始终是非严格递减的(即只保证前一项大于等于后一项的关系),每次都确保最大值在队首,这样直接返回队首就得到最值。

  3. 窗口移动时怎么处理队列中的值?

    当窗口已经建立时,每次移动窗口都会舍弃一个元素(窗口中的第一个元素)、新加入一个元素(窗口后面的第一个元素)。如果当前的队头最值正好是由要舍弃的元素产生的,那么要从队列中删除它。

代码实现如下:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int i = 0; i < k; i++) { // 还未形成窗口时
            //当队列不为空时,每次都和队列最后一个元素比较,如果比新元素小,就删除它。
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);//把新元素入队
        }
        res[0] = deque.peekFirst();//第一个滑动窗口的最大值就是队列的首元素
        for(int i = k; i < nums.length; i++) { // 形成窗口后
            if(deque.peekFirst() == nums[i - k])//每次移动窗口都会删除窗口最左侧元素,即下标i-k的元素,如果队头也等于这个元素就要一起删掉
                deque.removeFirst();
            //当队列不为空时,每次都和队列最后一个元素比较,如果比新元素小,就删除它。
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);//从队尾加入新元素
            res[i - k + 1] = deque.peekFirst();//记录本次滑动窗口中的最值。
        }
        return res;
    }
}

上一篇:

下一篇: