经典算法之滑动窗口-暴力解法+单调队列解法

快来打我* 2024-03-24 22:21 29阅读 0赞

作用：通常求最大(小)子数组/子序列/值

package com.xch.niuke;
    
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * 滑动窗口
     *
     * @author XuChenghe
     * @date 2023/8/27 12:18
     */
    public class Main001 {
        
        public static void main(String[] args) {
            // 最小值暴力解法
            int[] res1 = f1(new int[]{3, 1, 4, 5, 2, 6, 7}, 3);
            System.out.println(Arrays.toString(res1));
            // 最大值暴力解法
            int[] res2 = f2(new int[]{3, 1, 4, 5, 2, 6, 7}, 3);
            System.out.println(Arrays.toString(res2));
            
            // 最小值单调队列(递增)解法
            int[] res3 = f3(new int[]{3, 1, 4, 5, 2, 6, 7}, 3);
            System.out.println(Arrays.toString(res3));
            // 最大值单调队列(递减)解法
            int[] res4 = f4(new int[]{3, 1, 4, 5, 2, 6, 7}, 3);
            System.out.println(Arrays.toString(res4));
        }
        
        /**
         * 最小值暴力解法
         *
         * @param nums
         * @param k
         * @return
         */
        public static int[] f1(int[] nums, int k) {
            int[] res = new int[nums.length - k + 1];
            for (int i = k - 1; i < nums.length; i++) {
                res[i - k + 1] = nums[i];
                for (int j = i; j > i - k; j--) {
                    if (nums[j] < res[i - k + 1]) {
                        res[i - k + 1] = nums[j];
                    }
                }
            }
            return res;
        }
        
        /**
         * 最大值暴力解法
         *
         * @param nums
         * @param k
         * @return
         */
        public static int[] f2(int[] nums, int k) {
            int[] res = new int[nums.length - k + 1];
            for (int i = k - 1; i < nums.length; i++) {
                res[i - k + 1] = nums[i];
                for (int j = i; j > i - k; j--) {
                    if (nums[j] > res[i - k + 1]) {
                        res[i - k + 1] = nums[j];
                    }
                }
            }
            return res;
        }
        
        /**
         * 最小值单调队列(递增)解法
         *
         * @param nums
         * @param k
         * @return
         */
        public static int[] f3(int[] nums, int k) {
            List<Integer> list = new LinkedList<>();// 用List集合模拟Queue队列
            int[] res = new int[nums.length - k + 1];
            for (int i = 0; i < nums.length; i++) {
                if (i < k - 1) {
                    putAndPop3(null, list, nums[i]);
                } else if (i == k - 1) {
                    putAndPop3(null, list, nums[i]);
                    res[i - k + 1] = list.get(0);
                } else {
                    putAndPop3(nums[i - k], list, nums[i]);
                    res[i - k + 1] = list.get(0);
                }
            }
            return res;
        }
        
        /**
         * 维护单调队列(递增)
         *
         * @param head
         * @param list
         * @param num
         */
        public static void putAndPop3(Integer head, List<Integer> list, int num) {
            if (head != null && list.get(0) == head) {
                list.remove(0);
            }
            for (int i = list.size() - 1; i >= 0; i--) {
                if (list.get(i) > num) {// 注意相同的不要清除，否则有异常：-3, 4, 5, 8, 0, -1, 0, 1, 2, 0, 3, 4
                    list.remove(i);
                } else {
                    break;
                }
            }
            list.add(num);
        }
        
        /**
         * 最大值单调队列(递减)解法
         *
         * @param nums
         * @param k
         * @return
         */
        public static int[] f4(int[] nums, int k) {
            List<Integer> list = new LinkedList<>();// 用List集合模拟Queue队列
            int[] res = new int[nums.length - k + 1];
            for (int i = 0; i < nums.length; i++) {
                if (i < k - 1) {
                    putAndPop4(null, list, nums[i]);
                } else if (i == k - 1) {
                    putAndPop4(null, list, nums[i]);
                    res[i - k + 1] = list.get(0);
                } else {
                    putAndPop4(nums[i - k], list, nums[i]);
                    res[i - k + 1] = list.get(0);
                }
            }
            return res;
        }
        
        /**
         * 维护单调队列(递减)
         *
         * @param head
         * @param list
         * @param num
         */
        public static void putAndPop4(Integer head, List<Integer> list, int num) {
            if (head != null && list.get(0) == head) {
                list.remove(0);
            }
            for (int i = list.size() - 1; i >= 0; i--) {
                if (list.get(i) < num) {// 注意相同的不要清除，否则有异常
                    list.remove(i);
                } else {
                    break;
                }
            }
            list.add(num);
        }
        
    }