经典算法 — — 滑动窗口

红太狼 2024-04-06 12:43 89阅读 0赞

## 经典算法 — — 滑动窗口 ##

> ![在这里插入图片描述][73863e44025147e0886d9ee5c76bc9c7.png]

> ![在这里插入图片描述][76432550420e4e468be66bc6a5f9f0de.png]

### 1 返回每次窗口中的最大值 ###

![在这里插入图片描述][2900fb6d7a894fc19cd16e6a26f1c78e.png]

/**
     * @param arr 给定数组
     * @param w   窗口长度
     * @return
     */
    public static int[] getMaxByWindow(int[] arr, int w) {
        
        if (arr.length < w || arr == null || w < 1) {
        
            return null;
        }
        //记录每次窗口滑动的最大值
        int[] res = new int[arr.length - w + 1];
        //定义双向链表，用来计算最大值[里面存储的是下标值]
        LinkedList<Integer> qMax = new LinkedList<>();
        //用来标识res位置
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
        
            //如果后面想要进入队列的值比之前的值大，弹出之前的值
            while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[i]) {
        
                qMax.pollLast();
            }
            //记录合法下标值
            qMax.addLast(i);
            //如果超过窗口范围[w]
            if (qMax.peekFirst() == i - w) {
        
                qMax.pollFirst();
            }
            //记录最大值[窗口已经填满，可以记录]
            if (i >= w - 1) {
        
                res[index++] = arr[qMax.peekFirst()];
            }
        }
        return res;
    }

### 2 达标的子数组数量 ###

![在这里插入图片描述][d4c630263a9d41acaff39d23c12d58d8.png]

/**
     * @param arr 给定数组
     * @param sum arr的子数组中的最大-最小 <= sum
     * @return 返回满足条件的子数组数量
     */
    public static int num2(int[] arr, int sum) {
        
        if (arr == null || arr.length == 0 || sum < 0) {
        
            return 0;
        }
        int N = arr.length;
        //存放最小值[下标]
        LinkedList<Integer> minQueue = new LinkedList<>();
        //存放最大值[下标]
        LinkedList<Integer> maxQueue = new LinkedList<>();
        int R = 0;
        int count = 0;
        for (int L = 0; L < N; L++) {
        
            //子数组右边界尝试扩张
            while (R < N) {
        
                while (!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[R]) {
        
                    maxQueue.pollLast();
                }
                //添加R，一直往右边扩，直到不满足条件为止
                maxQueue.addLast(R);
                while (!minQueue.isEmpty() && arr[minQueue.peekLast()] >= arr[R]) {
        
                    minQueue.pollLast();
                }
                //记录的是下标的值
                minQueue.addLast(R);
                if (arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()] <= sum) {
        
                    R++;
                } else {
        
                    break;
                }
            }
            //最坏情况都满足，其拆分为子数组肯定也满足
            count += R - L;
            //该下标已经全部试完了，尝试以arr的下一个开始为头，寻找满足的子数组
            if(maxQueue.peekFirst() == L){
        
                maxQueue.pollFirst();
            }
            if(minQueue.peekFirst() == L){
        
                minQueue.pollFirst();
            }
        }
        return count;
    }

### 3 加油站出发点问题\[LeetCode - 134题\] ###

![在这里插入图片描述][91161ac4085e410b911b2203ddf39ab6.png]

class Solution {
        
        public int canCompleteCircuit(int[] gas, int[] cost) {
        
            boolean[] good = goodArray(gas, cost);
            for(int i = 0; i < good.length; i++){
        
                //找到满足条件的一个就可以了
                if(good[i]){
        
                    return i;
                }
            }
            return -1;
        }
    
        /**
         *   g:汽油数
         *   c:耗费油数
         */
        public boolean[] goodArray(int[] g, int[] c){
        
            int N = g.length;
            //两倍长度
            int M = N << 1;
            int[] arr = new int[M];
            for(int i = 0; i < N; i++){
        
                //两次前缀和
                arr[i] = g[i] - c[i];
                arr[i+N] = g[i] - c[i];
            }
            for(int i = 1; i < M; i++){
        
                //大数组的前缀和【之前的两倍长度】
                arr[i] = arr[i-1] + arr[i];
            }
            LinkedList<Integer> w = new LinkedList<>();
            for(int i = 0; i < N; i++){
        
                //找到前缀和数组中的最小值
                while(!w.isEmpty() && arr[w.peekLast()] >= arr[i]){
        
                    w.pollLast();
                }
                //存入下标
                w.addLast(i);
            }
            //记录从每个点出发，能否满足条件的情况
            boolean[] ans = new boolean[N];
            for(int offset = 0, i = 0, j = N; j < M; offset = arr[i++], j++){
        
                if(arr[w.peekFirst()] - offset >= 0){
        
                    //还原成原数组，看是否>=0
                    ans[i] = true;
                }
                //窗口移动【删除已经移除窗口的下标】
                if(w.peekFirst() == i){
        
                    w.pollFirst();
                }
                //找打窗口中最低点【值最小的】
                while(!w.isEmpty() && arr[w.peekLast()] >= arr[j]){
        
                    w.pollLast();
                }
                w.addLast(j);
            }
            return ans;
        }
    
    }

### 4 组成aim的最少货币数 ###

![在这里插入图片描述][8643cf02c4c14063ba6c66873817615e.png]

#### 4.1 递归写法 ####

public static int minCoins(int[] arr, int aim) {
        
    	return process(arr, 0, aim);
    }
    
    public static int process(int[] arr, int index, int rest) {
        
    	if (rest < 0) {
        
    		return Integer.MAX_VALUE;
    	}
    	if (index == arr.length) {
        
    		return rest == 0 ? 0 : Integer.MAX_VALUE;
    	} else {
        
    		int p1 = process(arr, index + 1, rest);
    		int p2 = process(arr, index + 1, rest - arr[index]);
    		if (p2 != Integer.MAX_VALUE) {
        
    			p2++;
    		}
    		return Math.min(p1, p2);
    	}
    }

#### 4.2 动态规划 ####

// dp3时间复杂度为：O(arr长度) + O(货币种数 * aim)
    // 优化需要用到窗口内最小值的更新结构
    public static int dp3(int[] arr, int aim) {
        
        if (aim == 0) {
        
            return 0;
        }
        // 得到info时间复杂度O(arr长度)
        Info info = getInfo(arr);
        int[] c = info.coins;
        int[] z = info.zhangs;
        int N = c.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 0;
        for (int j = 1; j <= aim; j++) {
        
            dp[N][j] = Integer.MAX_VALUE;
        }
        // 虽然是嵌套了很多循环，但是时间复杂度为O(货币种数 * aim)
        // 因为用了窗口内最小值的更新结构
        for (int i = N - 1; i >= 0; i--) {
        
            //mod相当于组号【组号限制】
            for (int mod = 0; mod < Math.min(aim + 1, c[i]); mod++) {
        
                // 当前面值 X
                // mod  mod + x   mod + 2*x   mod + 3 * x
                LinkedList<Integer> w = new LinkedList<>();
                w.add(mod);
                dp[i][mod] = dp[i + 1][mod];
                for (int r = mod + c[i]; r <= aim; r += c[i]) {
        
                    //跳着求
                    //最小值的更新结构
                    while (!w.isEmpty() && (dp[i + 1][w.peekLast()] == Integer.MAX_VALUE
                            || dp[i + 1][w.peekLast()] + compensate(w.peekLast(), r, c[i]) >= dp[i + 1][r])) {
        
                        w.pollLast();
                    }
                    w.addLast(r);
                    int overdue = r - c[i] * (z[i] + 1);
                    if (w.peekFirst() == overdue) {
        
                        w.pollFirst();
                    }
                    dp[i][r] = dp[i + 1][w.peekFirst()] + compensate(w.peekFirst(), r, c[i]);
                }
            }
        }
        return dp[0][aim];
    }
    
    // d c b a
    //补偿【d + 3、 c + 2、 b + 1、 a + 0】
    public static int compensate(int pre, int cur, int coin) {
        
        return (cur - pre) / coin;
    }

[73863e44025147e0886d9ee5c76bc9c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8211b62561c7487aa991b7ea98feb438.png
[76432550420e4e468be66bc6a5f9f0de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/0fc58b5cd97049e5ac5637251891a24e.png
[2900fb6d7a894fc19cd16e6a26f1c78e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/203f58dfaac74f64adcf9db7a58c9cad.png
[d4c630263a9d41acaff39d23c12d58d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/e96e10e9c1894b4d873199b5c40f1848.png
[91161ac4085e410b911b2203ddf39ab6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/c30fd5c810544a46af170573d33896e7.png
[8643cf02c4c14063ba6c66873817615e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8f064bf541d847b595605caf46720b8b.png