Java实现滑动窗口法

短命女 2023-10-09 18:34 15阅读 0赞

基本的滑动窗口法异常简单

逻辑基本为 在一个数组中 准备一个n大小的连续区域 比如\{5,7,8,3,2,4,8,0,6\}这个数组,我们用两个指针维持一个3大小的区域\{5,7,8\},每"走"一步 就把它的左指针 右指针向右移动一格,

这个移动的区域就叫做滑动窗口

#### 本文中的滑动窗口法 ####

用左右指针维护一个N大小的"窗口",这个窗口中存储的是元素的下标,加入数据时(移动右指针)要求窗口内严格由大到小(这里指的是下标对应的值),如果不满足该条件,如果新加入元素时不满足该条件就弹出之前的元素,直到这个窗口在加入新元素后满足由大到小,删除数据(移动左指针)时,由于左指针对应元素在之前的过程中可能弹出去了(如果没弹出去就在当前窗口的最左面),所以只判断最左面元素和窗口第一个元素是否相等即可.通过这个窗口 我们可以得到:在当前窗口范围中成为最大值的优先级

举个流程例子:

\{3,7,2,5,6,1,9,8\} 窗口为3

开始左指针右指针都是0所以先扩充长度到3

加入3 窗口为\{3\}

加入7 不满足由大到小 弹出3 变成\{\} 再加入7 \{7\}

加入2 满足由大到小 \{7,2\}

窗口大小为3了

加入5 不满足由大到小 弹出2 加入5 \{7,5\} 对应左下标已经没了 不用删除

加入6 不满足由大到小 弹出5 加入6\{7,6\} 对应左下标就是7 删除7->\{6\}

加入1 满足由大到小 \{6,1\} 对应左下标2已经没了 不用删除 删除

加入9 不满足由大到小 弹出7 6 1 加入9 \{9\} 对应左下标5已经没了 不用删除

加入8 满足由大到小 \{9,8\} 对应左下标6已经没了 不用删除

代码实现:

public static int [] SlidingWindow(int [] arr,int w) {
    	   if (arr == null || w < 1 || arr.length < w) {
    			return null;
    		}
    		// 其中放的是位置，头代表 （大->小）尾
    		LinkedList<Integer> qmax = new LinkedList<Integer>();
    		int[] res = new int[arr.length - w + 1];
    		int index = 0;
    		// L...R
    		//     i
    		for (int R = 0; R < arr.length; R++) { // 当前让 i -> [i] 进窗口 ， i 就是 r
    			// R -> 值  可以放在比他大的数后，或者空
    			while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
    				qmax.pollLast();
    			}
    			qmax.addLast(R);
    			// 数进来了
    			// 如果窗口没有形成W的长度之前，不弹出数字的
    			if (qmax.peekFirst() == R - w) {
    				qmax.pollFirst();
    			}
    			// 以上窗口更新做完了
    			if (R >= w - 1) {//每滑动一格都会把第一个值放到结果里面
    				res[index++] = arr[qmax.peekFirst()];
    			}
    		}
    		return res;