滑动窗口系列1-达标子数组

#达标子数组#

求达标子数组的数量
* 题目：给定一个数组，求满足子数组中最大值-最小值小于等于某个数的子数组的数量
* 例如[0,1,2,3]中求子数组中最大值-最小值小于等于 2的子数组的数量
* 结果为9,因为满足条件的只有[0,0] [0,1] [0,2] [1,1] [1,2] [1,3] [2,2] [2,3] [3,3]

题目对应的代码如下：

首先讨论暴力解，这种解法特别容易想，就是把所有的子数组进行枚举，例如：0~0,0~1,0~2,0~3, 0~4...2~2,2~2,2~3,2~4...然后依次找到每个子数组的最大值和最小值，根据二者之差判断是否达标，如果达标则总的数量加1，两层for循环的时间复杂度是O(N^2)，面试场没分

重点讨论第二种解法，也是本题的重要考察点：滑动窗口，对于滑动窗口解法来说，每个位置最多进一次窗口，也最多出一次窗口，所以时间复杂度是O(N)，这个已经是最好的解法了，你不可能所有的位置都没看完就找到所有答案

public class AllLessNumSubArray {/*** 暴力解，百分百正确，但是面试场上没分*/public static int right(int[] nums, int limit) {if(nums == null || nums.length == 0 || limit < 0) {return 0;}int result = 0;for(int i = 0; i < nums.length; i++) {int max = nums[i];int min = nums[i];for(int j = i; j < nums.length; j++) {max = Math.max(max, nums[j]);min = Math.min(min, nums[j]);if(max - min > limit) break;if(max - min <= limit) result ++;}}return result;}public static int better(int[] nums, int limit) {//不满足基本的条件，返回0个if(nums == null || nums.length == 0 || limit < 0) {return 0;}//数组的长度int N = nums.length;//创建最大值和最小值窗口，使用双端队列LinkedList<Integer> min = new LinkedList<>();LinkedList<Integer> max = new LinkedList<>();//L和R都从0开始，形成的区间是[L,R]左开右闭int R = 0;int L = 0;//最终结果统计int result = 0;//L,R的边界都是小于N，都是不回退的while(L < N) {while(R < N) {//如果当前最小值窗口中有数字大于要进去的R的位置的数字，依次弹出while(!min.isEmpty() && nums[min.peekLast()] >= nums[R]) {min.pollLast();}//R入最小值窗口min.addLast(R);//如果当前最大值窗口中有数字小于要进去的R的位置的数字，依次弹出while(!max.isEmpty() && nums[max.peekLast()] <= nums[R]) {max.pollLast();}//R入最小值窗口max.addLast(R);//当前窗口最大值-最小值如果不满足《=limit，终止，//如果满足条件R继续++，R是以L下标开始第一个不满足条件的if(nums[max.peekFirst()] - nums[min.peekFirst()] > limit) {break;} else {R++;}}//因为L马上要进行L++操作了，所以L位置马上过期，如果最大值或者最小值窗口的头部是L，则弹出头部if(max.peekFirst() == L) {max.pollFirst();}if(min.peekFirst() == L) {min.pollFirst();}//R是以L为起点的子数组中第一个不满足max-min<=limit的节点，所以数量加上(R - L)result += (R - L);L++;}return result;}}