黑龙江省机场建设集团官网网站民政局两学一做专题网站

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

暴力对数器
暴力对数器方法主要是用来和另一个方法互相校验正确性，所以不用考虑时间复杂度。
因为要求的是子数组中的最大值和子数组中的最小值相减 <= num。所以整体思路是这样：
求数组 0 ~ N - 1范围内，所有子数组，找到子数组中最小值，看相减后是否达标，如果达标，则count++进行计数。最后return count。
所有子数组挨个枚举，就是 0~ 0范围内子数组，0 ~ 1范围内子数组 0 ~ N - 1范围内子数组。
1 ~ 1范围内子数组，1 ~ 2 范围内子数组 1 ~ N - 1范围内子数组…。
每个范围内子数组进行枚举，需要两层for循环，找到每个子数组范围内的最大值和最小值，额外需要1层for循环，所以时间复杂度是 $O（N^3）$。

代码

 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++) {min = Math.min(min, arr[i]);max = Math.max(max, arr[i]);}if (max - min <= sum) {count++;}}}return count;}

滑动窗口算法
采用滑动窗口算法的时间复杂度是$O（N）$，因为窗口不可回退，所以只需要一次遍历即可找出所有符合条件的子数组。
这道题中需要2个窗口，一个维护L…R范围内的最大值，一个维护L…R范围内的最小值。而在看代码之前，需要达成这样的2个共识：

1. 如果L…R范围内 max - min <= num，那么L…R范围内所有子数组都满足 max - min <= num，都会达标。
2. 如果L…R范围内 max - min > num，那么无论R继续向右扩窗口或者L继续向左阔窗口，那L…R范围内子数组依然不达标。

解释1：
因为max - min <= num，所以L…R 范围内剩余子数组相减，子数组范围内的两个数一定是 < max && > min的，最大值变小了，最小值变大了，所以一定会<= num。
解释2：
因为max - min > num，根据滑动窗口的特性，在维护L…R范围内最大值的双端队列中，后进来的数一定是>=当前双端队列中的值才会进行替换，在维护L…R范围内最小值的双端队列中，后进来的数一定是<=当前双端队列中的值才会进行替换。 所以无论向右或者向左，范围内子数组一定依然不达标。

达成这两个共识之后，代码就简单了很多，在维护双端队列特性的同时，如果满足 max - min <= num，则R向右移，直到不满足 max - min <= num为止。碰见一次不满足，则计算一次当前子数组的个数，直到循环完成。

代码

public static int num(int[] arr, int sum) {if (arr == null || arr.length == 0  || sum < 0) {return 0;}LinkedList<Integer> minWindow = new LinkedList<>();LinkedList<Integer> maxWindow = new LinkedList<>();int R = 0;int count = 0;int N = arr.length;for (int L = 0; L < N; L++) {while (R < N) {//如果max双端队列不为null，并且队列尾端值<=当前值，则弹出while (!maxWindow.isEmpty() && arr[maxWindow.peekLast()] <= arr[R]) {maxWindow.pollLast();}maxWindow.addLast(R);//如果min双端队列不为null，并且队列尾端值>=当前值，则弹出while (!minWindow.isEmpty() && arr[minWindow.peekLast()] >= arr[R]) {minWindow.pollLast();}minWindow.addLast(R);//如果满足条件，则R一直++， 直到不满足条件为止if (arr[maxWindow.peekFirst()] - arr[minWindow.peekFirst()] <= sum) {R++;} else {break;}}//看R - L范围内共有多少个子数组count += R - L;//因为这两个判断走完L就要进行++//所以需要判断当前双端队列中头部值是否要过期了if (maxWindow.peekFirst() == L) {maxWindow.pollFirst();}if (minWindow.peekFirst() == L) {minWindow.pollFirst();}}return count;}

测试
随机生成数组和sum，采用大数据样本量进行测试，用上面两个方法来相互验证。

public static int[] generateRandomArray(int maxLength, int maxValue) {int[] arr = new int[(int) ((maxLength + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random());}return arr;}public static void main(String[] args) {int maxLength = 40;int maxValue = 10000;int sum = 10000;int testNum = 1000000;System.out.println("测试开始");for (int i = 0; i < testNum; i++) {int[] arr = generateRandomArray(maxLength, maxValue);sum = (int) ((sum + 1) * Math.random());int ans1 = right(arr, sum);int ans2 = num(arr, sum);if (ans1 != ans2) {for (int num : arr) {System.out.print(num + " ");}System.out.println();System.out.println("sum : " + sum);System.out.println("ans1 : " + ans1);System.out.println("ans2 : " + ans2);System.out.println("Oops!!");break;}}System.out.println("测试结束");}