滑动窗口问题

柔光的暖阳◎ 2023-06-22 07:27 16阅读 0赞

# 滑动窗口问题 #

--------------------

1.  滑动窗口解决思路
2.  生成窗口最大值数组
3.  求一个数组中最大值减去最小值小于或等于 num 的子数组数量

--------------------

### 1. 滑动窗口解决思路 ###

准备一个双端队列，双端队列存放着数组中的下标值。

假设当前为 arr\[i\]，则放入规则如下：

*  left 和 right 指针都只会向右移动，不会回退。
 *  right 右滑，窗口加数：  
    1）如果 queue 为空，直接把下标 i 放入 queue 中；  
    2）如果 queue 不为空，取出当前 queue 队尾存放的下标 j。如果 arr\[j\] > arr\[i\]，则直接把 i 放入队尾；  
    3）如果 arr\[j\] <= arr\[i\]，则一直从 queue 的队尾弹出下标，直到某个下标在 queue 中的对应值大于 arr\[i\]，然后把 i 放入队尾
 *  left 右滑，窗口减数：  
    1）看弹出的 left 是否与队列头相等，如果相等，说明这个队列头已经不在窗口内了，所以弹出 queue 当前的队首元素 。

双端队列的队头就是当前窗口最大值的下标。

--------------------

### 2. 生成窗口最大值数组 ###

题目描述：【题目】有一个整形数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向最右边滑一个位置。

例如，数组为\[4,3,5,4,3,3,6,7\],窗口大小为3时，

\[4 3 5\] 4 3 3 6 7 窗口最大值为5

4 \[3 5 4\] 3 3 6 7 窗口最大值为5

4 3 \[5 4 3\] 3 6 7 窗口最大值为5

4 3 5 \[4 3 3\] 6 7 窗口最大值为4

4 3 5 4 \[3 3 6\] 7 窗口最大值为6

4 3 5 4 3 \[3 6 7\] 窗口最大值为7

如果数组长度为n,窗口大小为w，则一共产生n-w+1个窗口的最大值。请实现一个函数：

输入：整型数组arr, 窗口大小为w.

输出：一个长度为n-w+1的数组res，res\[i\]表示每一种窗口状态下的最大值。

以本题为例，结果应该返回\{5,5,5,4,6,7\}。

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

--------------------

### 3. 求一个数组中最大值减去最小值小于或等于 num 的子数组数量 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]

public static int getNum(int[] arr, int num) {
        
            if (arr == null || arr.length == 0) {
        
                return 0;
            }
            LinkedList<Integer> qmin = new LinkedList<>();
            LinkedList<Integer> qmax = new LinkedList<>();
            int L = 0;
            int R = 0;
            int res = 0;
            while (L < arr.length) {
        
                while (R < arr.length) {
        
                    if (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R]) {
        
                        qmin.pollLast();
                    }
                    qmin.addLast(R);
                    if (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
        
                        qmax.pollLast();
                    }
                    qmax.addLast(R);
                    if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num) {
        
                        break;
                    }
                    R++;
                }
                if (qmin.peekFirst() == L) {
        
                    qmin.pollFirst();
                }
                if (qmax.peekFirst() == L) {
        
                    qmax.pollFirst();
                }
                res += R - L;
                L++;
            }
            return res;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191215101309358.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70