mzoe666888

V1

2022/04/29阅读:23主题:兰青

滑动窗口

一、滑动窗口是什么

滑动窗口是一种想象出来的数据结构:

  • 滑动窗口有左边界L和右边界R
  • 在数组或者字符串或者一个序列上,记为S,窗口就是S[L..R]这一部分
  • L往右滑意味着一个样本出了窗口,R往右滑意味着一个样本进了窗口
  • L和R都只能往右滑

滑动内最大值和最小值的更新结构:

  • 窗口不管L还是R滑动之后,都会让窗口呈现新状况
  • 如何能够更快的得到窗口当前状况下的最大值和最小值?
  • 最好平均下来复杂度能做到O(1)
  • 利用单调双端队列!

任何时刻:

R++,R往右动(滑),数会从右侧进窗口

L++,L往右动(滑),数会从左侧出窗口

原则:L不能跑到(滑到)R的右边去,需要保持维持住这个窗口,动态的从右侧进数,动态的从左侧出数,这就是规定好的窗口,这个窗口是动态的

如果在滑动的窗口上,求窗口内的最大值?

如果每次在窗口内,通过遍历求最大值,形成一个窗口,遍历一下,形成一个窗口,遍历一下,这种方法很低效。那有没有一种好的办法,在窗口形成的时候,能迅速得到最大值,当一个数进窗口时,能迅速更新窗口内最大值,当一个数出窗口时,能迅速更新窗口内最大值,这种数据结构就是滑动窗口(SlidingWindow)

滑动窗口最大值问题:利用双端队列,头到尾按照从大到小的原则,新建来的数从尾部进,如果双端队列中尾部的数大于新进来的数,则新建来的数直接从尾部进,如果双端队列中尾部的数小于等于新进来的数,则弹出尾部的数(相等也弹出),直到新进来的数小于尾部的数停止,此时新进来的数再从尾部进入

双端队列存放的是数组的下标,因为通过下标能从数组中获得值

为什么要双端队列?双端队列的含义:如果此时滑动窗口依次缩小时,哪些位置的数会依次成为窗口内的最大值

窗口运动的过程中,一个数最多进一次,最多出一次(从左出或从右出),双端队列更新的总代价O(N)

窗口的最大值为双端队列头部位置,查询很快O(1)

二、滑动窗口的实现

假设一个固定大小为W的窗口,依次划过arr,

返回每一次滑出状况的最大值

例如,arr = [4,3,5,4,3,3,6,7], W = 3

返回:[5,5,5,4,6,7]

1、暴力实现

遍历求最大值

public static int[] right(int[] arr, int w) {
    if (arr == null || w < 1 || arr.length < w) {
        return null;
    }
    int N = arr.length;
    int[] res = new int[N - w + 1];
    int index = 0;
    int L = 0;
    int R = w - 1;
    while (R < N) {
        int max = arr[L];
        for (int i = L + 1; i <= R; i++) {
            max = Math.max(max, arr[i]);
        }
        res[index++] = max;
        L++;
        R++;
    }
    return res;
}

2、双端队列实现

双端队列里放数组的下标,窗口过期点怎么判断?

只需要一个指针R就可以实现窗口大小的规模,当来到R位置时,R-w就是窗口过期的位置(L),怎么判断窗口是否过期?通过 qmax.peekFirst() == R - w 来判断,如果R-w的下标等于双端队列头部的下标,则过期弹出

窗口规模形成时收集答案

public static int[] getMaxWindow(int[] arr, int w) {
    if (arr == null || w < 1 || arr.length < w) {
        return null;
    }
    // qmax 窗口最大值的更新结构
    // 放下标
    LinkedList<Integer> qmax = new LinkedList<>();
    int[] res = new int[arr.length - w + 1];
    int index = 0;
    for (int R = 0; R < arr.length; R++) {
        while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
            qmax.pollLast();
        }
        qmax.addLast(R);
        if (qmax.peekFirst() == R - w) { // 过期位置
            qmax.pollFirst();
        }
        // 窗口预热,达到窗口大小时收集答案
        // 现在是否形成了正常窗口,窗口在未形成时,窗口属于培养期,不需要收集答案
        if (R >= w - 1) {
            res[index++] = arr[qmax.peekFirst()];
        }
    }
    return res;
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1