左神算法笔记——滑动窗口

问题描述

介绍窗口以及窗口内最大值最小值的更新结构（单调双向队列）

简单描述对问题的理解：给定一个数组arr,给出数组中窗口的边界L和R，求出数组L到R位置中的元素最大值。

思路分析

借用一个双端队列，队列只存储数组中元素的索引，不断滑动更新窗口，调正双端队列中元素的值，使其永远保证从大到小的顺序。

• 如果数组的右指针向右移动，则将元素按照添加条件添加到双端队列尾部。这个如果待添加的元素>=双端队列尾部的值，则不断弹出队列尾部元素，直到满足由大到小的条件。
• 如果数组的左指针向右移动，则检查队列头索引与当前左指针是否一致，如果一致则弹出。

代码

// 获取窗口内的最大值
public class Code_01_MaxWindow {

    public static int getMaxValue(int[] arr, int l, int r) {
        if(l < 0 || r >= arr.length || l > r) {
            throw new RuntimeException("参数输出有误！");
        }
        // 创建一个双端队列
        LinkedList<Integer> list = new LinkedList<>();
        // 从数组l位置向队列中添加元素
        for (int i = l; i <= r; i++) {
            while(!list.isEmpty() && arr[list.peekLast()] <= arr[i]){
                list.pollLast();  // 从尾部弹出元素
            }
            list.addLast(i);
        }
        return arr[list.peekFirst()];
    }

    public static void main(String[] args) {
        int[] arr = {1,2,5,3,7,8,4};
        System.out.println(getMaxValue(arr,0,6));
    }
}

---

滑动窗口衍生题

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如，数组为【4,3,5,4,3,3,6,7】，窗口大小为3时：
窗口数组 -------------------------------- 最大值
[4 3 5] 4 3 3 6 7 5 ----------------------- 5
4 [3 5 4] 3 3 6 7 5 ----------------------- 5
4 3 [5 4 3] 3 6 7 5 ----------------------- 5
4 3 5 [4 3 3] 6 7 4 ----------------------- 4
4 3 5 4 [3 3 6] 7 6 ----------------------- 6
4 3 5 4 3 [3 6 7] 7 ----------------------- 7
4 3 5 4 3 3 [6 7 7] ----------------------- 7
如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。返回每个窗口中的最大值。

思路分析

同理，使用借用双端队列来实现。

• 值得注意的是，当数组指针还没有到w的时候是不用左任何操作的，因为还没有窗口的大小

代码

    public static int[] getMaxWindow(int[] arr, int w) {
        if(arr == null || w < 1 || w > arr.length) return null;
        // 创建双端队列
        LinkedList<Integer> list = new LinkedList<Integer>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            while(!list.isEmpty() && arr[list.peekLast()] <= arr[i]){
                list.pollLast();
            }
            list.addLast(i);
            if(list.peekFirst() == i - w){
                list.pollFirst();
            }
            if(i >= w - 1){
                res[index++] = arr[list.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,5,3,7,8,4};
        System.out.println(Arrays.toString(getMaxWindow(arr,3)));
    }

---

滑动窗口衍生题二

最大值减去最小值小于等于num的子数组数量
要求： 如果数组长度为N，请实现时间复杂度为O(N)的解法。

思路

解法一： 暴力枚举（不推荐）

• 遍历所有子数组的情况，计算当前数组的最大值和最小值的差值，如果满足条件则结果集加1。

解法二： 滑动窗口

• 首先必须明确两个结论，如果L-R范围内的子数组满足条件，则L-R范围内的任意子数组都满足条件；如果L-R范围内的子数组不满足条件，则包含L-R数组的所有数组都不满足条件。

• 那么根据这种结论，具体实现思路如下：

  
  image.png

代码

    public static int getNum(int[] arr, int num){
        if(arr == null || arr.length == 0) return 0;
        // 创建两个双端队列
        LinkedList<Integer> dpMin = new LinkedList<Integer>();
        LinkedList<Integer> dpMax = new LinkedList<Integer>();
        // 设置左右指针
        int res = 0;
        int L = 0;
        int R = 0;
        while(L < arr.length){
            while(R < arr.length){
                // 更新两个双端队列
                while(!dpMax.isEmpty() && arr[dpMax.peekLast()] <= arr[R]){
                    dpMax.pollLast();
                }
                dpMax.addLast(R);
                while(!dpMin.isEmpty() && arr[dpMin.peekLast()] >= arr[R]){
                    dpMin.pollLast();
                }
                dpMin.addLast(R);
                if(arr[dpMax.peekFirst()] - arr[dpMin.peekFirst()] > num){
                    break;
                }
                R++;
            }
            // 去除当前L位置的影响，L右移
            if(dpMin.peekFirst() == L){
                dpMin.pollFirst();
            }
            if(dpMax.pollFirst() == L){
                dpMax.pollFirst();
            }
            res += R - L;
            L++;
        }
        return res;
    }