参考 最大值减去最小值小于或等于num的子数组数量 Sliding Window Maximum

Description

给定数组arr和整数num，求arr的连续子数组中满足：其最大值减去最小值的结果大于num的个数。请实现一个时间复杂度为O(length(arr))的算法。

Input

输入第一行为测试用例个数。每一个用例有若干行，第一行为数组，每一个数用空格隔开，第二行为num。

Output

输出一个值。

Sample Input 1

Sample Output 1

如题目所示

|3-6|=3>2 即: 36 364 3643 36432都满足条件.即:满足条件的个数是len(arr) - 6的下标

36 4 3 2 即把36 当做一个整体 ,以3开头,并且包含36的就是答案的一部分. 个数为 5-1 =4个

|6-3|=3>2 即: 643 6432满足条件

3 643 2 即把643 当做一个整体 ,以6开头,并且包含643的就是答案的一部分. 个数为 5-3 =2个

共有4 + 2 =6个

因此答案是6

即: 以i开头,并包含一个区间[x,y] 满足|x-y| > num ,这样就可以做到不重不漏的全部都统计完毕

可以使用暴力的解法o(n2) 即每个数都找一遍有没有下一个数和它的差的绝对值>num有就计算数量. python

另一种是利用双向队列来储存最大值和最小值

1、生成两个双端队列qmax 和qmin. 2、令j不断向右移动（j++）,表示arr[i…j]一直向右扩大，并不断更新qmax和qmin结构，保证qmax和qmin始终维持动态窗口最大值和最小值的更新结构。 3、当进行完步骤2，令i向右移动一个位置并对qmax和qmin做出相应的更新做出相应的更新。 4、根据步骤2，步骤3，依次求出以arr[0],arr[1],arr[2]……、arr[N-1] 作为第一个元素的子数组中满足条件的数量分别有多少，累加起来起来的数量就是最终的结果。

举个例子

如: arr= [6 8 4 2 1] num =2

第一次满足条件时是当i=0 j=3 时: 6 8 4 2 1 ,8-4=4>2 注意:第一次不是6 2 (按照代码逻辑,8比6大,6是会被弹出栈的,会把8压入栈,那么6 2 的情况怎么统计呢?见下文.)

这个时候计算len(arr) - j = 5 - 2 =3 个,对应的具体例子为684 6842 68421 注意:因为i=0,计算的时候其实是计算以6开头的,以2结尾的子数组的个数.因此 6 2 的情况就已经被包括在内了

第二次满足条件时是当i=1 j=3 时: 6 8 4 2 1 , 8-4 = 4>2

这个时候计算len(arr) - j = 5 - 3 =2 个,对应的具体例子为84 842 8421 注意:因为i=1,计算的时候其实是计算以8开头的,以2结尾的子数组的个数.

第二次满足条件时是当i=2 j=5 时: 6 8 4 2 1 , 4-1= 3>2

这个时候计算len(arr) - j = 5 - 4 =1个,

共3+3+1 =7个

java