滑动窗口是什么？

滑动窗口是一种想象出来的数据结构：
滑动窗口有左边界L和有边界R
在数组或者字符串或者一个序列上，记为S，窗口就是S[L…R]这一部分
L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口
L和R都只能往右滑

滑动内最大值和最小值的更新结构

窗口不管L还是R滑动之后，都会让窗口呈现新状况，
如何能够更快的得到窗口当前状况下的最大值和最小值？
最好平均下来复杂度能做到O(1)
利用单调双端队列！

习题1 假设一个固定大小为W的窗口，依次划过arr，返回每一次滑出状况的最大值例 如，arr = [4,3,5,4,3,3,6,7], W = 3返回：[5,5,5,4,6,7]

// 暴力的对数器方法public static int[] right(int[] arr, int w) {if (arr == null || w < 1 || arr.length < w) {return null;}int N = arr.length;int[] res = new int[N - w + 1];int index = 0;int L = 0;int R = w - 1;while (R < N) {int max = arr[L];for (int i = L + 1; i <= R; i++) {max = Math.max(max, arr[i]);}res[index++] = max;L++;R++;}return res;}public static int[] getMaxWindow(int[] arr, int w) {if (arr == null || w < 1 || arr.length < w) {return null;}// qmax 窗口最大值的更新结构// 放下标LinkedList<Integer> qmax = new LinkedList<Integer>();int[] res = new int[arr.length - w + 1];int index = 0;for (int R = 0; R < arr.length; R++) {while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {qmax.pollLast();}qmax.addLast(R);if (qmax.peekFirst() == R - w) {qmax.pollFirst();}if (R >= w - 1) {res[index++] = arr[qmax.peekFirst()];}}return res;}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) (Math.random() * (maxValue + 1));}return arr;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}public static void main(String[] args) {int testTime = 100000;int maxSize = 100;int maxValue = 100;System.out.println("test begin");for (int i = 0; i < testTime; i++) {int[] arr = generateRandomArray(maxSize, maxValue);int w = (int) (Math.random() * (arr.length + 1));int[] ans1 = getMaxWindow(arr, w);int[] ans2 = right(arr, w);if (!isEqual(ans1, ans2)) {System.out.println("Oops!");}}System.out.println("test finish");}

习题2 给定一个整型数组arr，和一个整数num 某个arr中的子数组sub，如果想达标，必须满足：sub中最大值 – sub中最小值 <= num，返回arr中达标子数组的数量

// 暴力的对数器方法public static int right(int[] arr, int sum) {if (arr == null || arr.length == 0 || sum < 0) {return 0;}int N = arr.length;int count = 0;for (int L = 0; L < N; L++) {for (int R = L; R < N; R++) {int max = arr[L];int min = arr[L];for (int i = L + 1; i <= R; i++) {max = Math.max(max, arr[i]);min = Math.min(min, arr[i]);}if (max - min <= sum) {count++;}}}return count;}public static int num(int[] arr, int sum) {if (arr == null || arr.length == 0 || sum < 0) {return 0;}int N = arr.length;int count = 0;LinkedList<Integer> maxWindow = new LinkedList<>();LinkedList<Integer> minWindow = new LinkedList<>();int R = 0;for (int L = 0; L < N; L++) {while (R < N) {while (!maxWindow.isEmpty() && arr[maxWindow.peekLast()] <= arr[R]) {maxWindow.pollLast();}maxWindow.addLast(R);while (!minWindow.isEmpty() && arr[minWindow.peekLast()] >= arr[R]) {minWindow.pollLast();}minWindow.addLast(R);if (arr[maxWindow.peekFirst()] - arr[minWindow.peekFirst()] > sum) {break;} else {R++;}}count += R - L;if (maxWindow.peekFirst() == L) {maxWindow.pollFirst();}if (minWindow.peekFirst() == L) {minWindow.pollFirst();}}return count;}// for testpublic static int[] generateRandomArray(int maxLen, int maxValue) {int len = (int) (Math.random() * (maxLen + 1));int[] arr = new int[len];for (int i = 0; i < len; i++) {arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));}return arr;}// for testpublic static void printArray(int[] arr) {if (arr != null) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}}public static void main(String[] args) {int maxLen = 100;int maxValue = 200;int testTime = 100000;System.out.println("测试开始");for (int i = 0; i < testTime; i++) {int[] arr = generateRandomArray(maxLen, maxValue);int sum = (int) (Math.random() * (maxValue + 1));int ans1 = right(arr, sum);int ans2 = num(arr, sum);if (ans1 != ans2) {System.out.println("Oops!");printArray(arr);System.out.println(sum);System.out.println(ans1);System.out.println(ans2);break;}}System.out.println("测试结束");}

习题3 加油站的良好出发点问题

// 这个方法的时间复杂度O(N)，额外空间复杂度O(N)public static int canCompleteCircuit(int[] gas, int[] cost) {boolean[] good = goodArray(gas, cost);for (int i = 0; i < gas.length; i++) {if (good[i]) {return i;}}return -1;}public static 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];}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) {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 arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，返回组成aim的最少货币数 注意：因为是求最少货币数，所以每一张货币认为是相同或者不同就不重要了

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);}}// dp1时间复杂度为：O(arr长度 * aim)public static int dp1(int[] arr, int aim) {if (aim == 0) {return 0;}int N = arr.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;}for (int index = N - 1; index >= 0; index--) {for (int rest = 0; rest <= aim; rest++) {int p1 = dp[index + 1][rest];int p2 = rest - arr[index] >= 0 ? dp[index + 1][rest - arr[index]] : Integer.MAX_VALUE;if (p2 != Integer.MAX_VALUE) {p2++;}dp[index][rest] = Math.min(p1, p2);}}return dp[0][aim];}public static class Info {public int[] coins;public int[] zhangs;public Info(int[] c, int[] z) {coins = c;zhangs = z;}}public static Info getInfo(int[] arr) {HashMap<Integer, Integer> counts = new HashMap<>();for (int value : arr) {if (!counts.containsKey(value)) {counts.put(value, 1);} else {counts.put(value, counts.get(value) + 1);}}int N = counts.size();int[] coins = new int[N];int[] zhangs = new int[N];int index = 0;for (Entry<Integer, Integer> entry : counts.entrySet()) {coins[index] = entry.getKey();zhangs[index++] = entry.getValue();}return new Info(coins, zhangs);}// dp2时间复杂度为：O(arr长度) + O(货币种数 * aim * 每种货币的平均张数)public static int dp2(int[] arr, int aim) {if (aim == 0) {return 0;}// 得到info时间复杂度O(arr长度)Info info = getInfo(arr);int[] coins = info.coins;int[] zhangs = info.zhangs;int N = coins.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;}// 这三层for循环，时间复杂度为O(货币种数 * aim * 每种货币的平均张数)for (int index = N - 1; index >= 0; index--) {for (int rest = 0; rest <= aim; rest++) {dp[index][rest] = dp[index + 1][rest];for (int zhang = 1; zhang * coins[index] <= aim && zhang <= zhangs[index]; zhang++) {if (rest - zhang * coins[index] >= 0&& dp[index + 1][rest - zhang * coins[index]] != Integer.MAX_VALUE) {dp[index][rest] = Math.min(dp[index][rest], zhang + dp[index + 1][rest - zhang * coins[index]]);}}}}return dp[0][aim];}// 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--) {for (int mod = 0; mod < Math.min(aim + 1, c[i]); mod++) {// 当前面值 X// mod  mod + x   mod + 2*x   mod + 3 * xLinkedList<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];}public static int compensate(int pre, int cur, int coin) {return (cur - pre) / coin;}// 为了测试public static int[] randomArray(int N, int maxValue) {int[] arr = new int[N];for (int i = 0; i < N; i++) {arr[i] = (int) (Math.random() * maxValue) + 1;}return arr;}// 为了测试public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// 为了测试public static void main(String[] args) {int maxLen = 20;int maxValue = 30;int testTime = 300000;System.out.println("功能测试开始");for (int i = 0; i < testTime; i++) {int N = (int) (Math.random() * maxLen);int[] arr = randomArray(N, maxValue);int aim = (int) (Math.random() * maxValue);int ans1 = minCoins(arr, aim);int ans2 = dp1(arr, aim);int ans3 = dp2(arr, aim);int ans4 = dp3(arr, aim);if (ans1 != ans2 || ans3 != ans4 || ans1 != ans3) {System.out.println("Oops!");printArray(arr);System.out.println(aim);System.out.println(ans1);System.out.println(ans2);System.out.println(ans3);System.out.println(ans4);break;}}System.out.println("功能测试结束");System.out.println("==========");int aim = 0;int[] arr = null;long start;long end;int ans2;int ans3;System.out.println("性能测试开始");maxLen = 30000;maxValue = 20;aim = 60000;arr = randomArray(maxLen, maxValue);start = System.currentTimeMillis();ans2 = dp2(arr, aim);end = System.currentTimeMillis();System.out.println("dp2答案 : " + ans2 + ", dp2运行时间 : " + (end - start) + " ms");start = System.currentTimeMillis();ans3 = dp3(arr, aim);end = System.currentTimeMillis();System.out.println("dp3答案 : " + ans3 + ", dp3运行时间 : " + (end - start) + " ms");System.out.println("性能测试结束");System.out.println("===========");System.out.println("货币大量重复出现情况下，");System.out.println("大数据量测试dp3开始");maxLen = 20000000;aim = 10000;maxValue = 10000;arr = randomArray(maxLen, maxValue);start = System.currentTimeMillis();ans3 = dp3(arr, aim);end = System.currentTimeMillis();System.out.println("dp3运行时间 : " + (end - start) + " ms");System.out.println("大数据量测试dp3结束");System.out.println("===========");System.out.println("当货币很少出现重复，dp2比dp3有常数时间优势");System.out.println("当货币大量出现重复，dp3时间复杂度明显优于dp2");System.out.println("dp3的优化用到了窗口内最小值的更新结构");}