窗口内最大值最小值更新

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

[6 4 2 3 5 7 0 5]
用双端队列进行更新
[6 4 2]  [6 4 3] [6 5] [7] [7 0] [7 5]
含义：当窗口开始缩短时，哪些位置的数会依次成为max

题目一 固定窗口最大值

假设一个固定大小为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中达标子数组的数量

如果L到R上已经达标了，那么内部的子数组一定达标 
如果L到R上已经不达标了，那么往左扩或者右扩一定不达标

	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++) {
            //[L.....R)
			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;
	}

题目三

题目四

arr是货币数组，其中的值都是正数。再给定-个正数aim。
每个值都认为是一-张货币，
返回组成aim的最少货币数
注意:
因为是求最少货币数，所以每一张货币认为是相同或者不同就不重要了