【算法&数据结构体系篇class24】：滑动窗口技巧

小鱼儿 2024-03-24 17:04 39阅读 0赞

### 一、滑动窗口是什么 ###

> 滑动窗口是一种想象出来的数据结构：
> 
> 滑动窗口有左边界L和有边界R
> 
> 在数组或者字符串或者一个序列上，记为S，窗口就是S\[L..R\]这一部分
> 
> L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口
> 
> L和R都只能往右滑

### 二、滑动内最大值和最小值的更新结构 ###

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

###  ###

### 三、题目一 ###

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

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

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

返回：\[5,5,5,4,6,7\]

package class24;
    
    import java.util.LinkedList;
    
    /**
     * 假设一个固定大小为W的窗口，依次划过arr，
     * 返回每一次滑出状况的最大值
     * 例如，arr = [4,3,5,4,3,3,6,7], W = 3
     * 返回：[5,5,5,4,6,7]
     */
    public class SlidingWindowMaxArray {
    
        //滑动窗口技巧   定义一个双端队列linkedlist辅助滑动弹出元素加入元素 保存数组元素的下标
        public static int[] getMaxWindow(int[] arr, int w){
            //边界判断 如果数组空 窗口大小0  窗口大小大于数组 都是无效的 返回空
            if(arr == null || w < 1 || arr.length < w) return null;
    
            //定义一个双端队列 qmax  从大到小排序 头部大 尾部小 保存的是数组的元素索引 不是元素数值 因为根据滑动要把溢出的元素弹出 需要获取到索引
            LinkedList<Integer> qmax = new LinkedList<>();
    
            //定义一个数组 保存结果 每个窗口 3个元素中的最大值。 这里数组的长度是固定的
            //数组长度8  窗口w=3 那么第一个窗口就是来到 4，3，5 返回5，第二个窗口时3，5，4 返回5，
            // 第三个窗口 5，4，3 返回5...依次类推最后结果是[5,5,5,4,6,7] 长度6 即arr长度8 - w3 +1 =6
            int[] res = new int[arr.length - w + 1];
    
            int index =0;  //定义结果集的下标从左到右
            //从左到右开始遍历 直到遍历完整个数组
            for(int r = 0; r < arr.length; r++){
                //题意要求每个窗口返回其最大值 所以我们元素进队列，需要把前面小于等于的值都弹出来
                //元素索引入队列前  需要判断 qmax非空时，如果当前数组arr[r]值大于等于队列尾部，
                //就将尾部索引值弹出，直到队列前面的元素值大于当前arr[r]值即可
                while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[r]){
                    qmax.pollLast();
                }
                //队列中弹出后，就可以将当前r索引入队列
                qmax.addLast(r);
    
                //判断当前队列头部是否需要弹出 一个窗口3长度 当r来到3时，窗口值就 1，2，3 就需要将r-w=0位置弹出
                //如果r=5 那么窗口就是 3，4，5 队列中就需要将小于3的索引都去掉 因为要确保队列是保持着当前窗口最大值索引在队列头部的 超过了窗口的就要弹出
                if(qmax.peekFirst() == r - w){
                    qmax.pollFirst();   //队列头部最大值的索引值如果不在当前窗口内 就需要弹出 避免影响当前窗口实际的最大值索引
                }
    
                //判断什么时候开始填入结果集，当我们r位置到达w窗口3个值长度时 就是第一个窗口的值需要填入了 0，1，2 也就是r=2时
                if (r  >= w - 1 ){
                    //也就是r>=2 后面开始每个值对应一个窗口 窗口最大值就是当前队列的头部 头部保持最大值的索引
                    res[index++] = arr[qmax.peekFirst()];
                }
            }
            return res;
        }
    
        // 暴力的对数器方法
        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;
        }
    
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) (Math.random() * (maxValue + 1));
            }
            return arr;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i&#