[数据结构与算法]算法数据结构（二十二）----滑动窗口

滑动窗口是什么？

滑动窗口是一种想象出来的数据结构：

滑动窗口有左边界L和有边界R

在数组或者字符串或者一个序列上，记为S，窗口就是S[L..R]这一部分

L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口

L和R都只能往右滑

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

窗口不管L还是R滑动之后，都会让窗口呈现新状况，

如何能够更快的得到窗口当前状况下的最大值和最小值？

最好平均下来复杂度能做到O(1)

利用单调双端队列！

?题目一

假设一个固定大小为W的窗口，依次划过arr，

返回每一次滑出状况的最大值

例如，arr = [4,3,5,4,3,3,6,7], W = 3

返回：[5,5,5,4,6,7]

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;
	}

?题目二

?给定一个整型数组arr，和一个整数num

某个arr中的子数组sub，如果想达标，必须满足：

sub中最大值 – sub中最小值 <= num，

返回arr中达标子数组的数量

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;
	}

题目三

https://leetcode.com/problems/gas-station

?加油站的良好出发点问题

数组A表示加油站能加多少油，数组B表示加油站到下一个加油站锁消耗多少油

// 这个方法的时间复杂度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;
	}

题目四

arr是货币数组，其中的值都是正数。再给定一个正数aim。

每个值都认为是一张货币，

返回组成aim的最少货币数

注意：

因为是求最少货币数，所以每一张货币认为是相同或者不同就不重要了

?

// 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 * 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];
	}