子数组最大和最小值的差大等小于给定值(h1:1.1)

给定数组arr和整数num，求arr的连续子数组中满足：其最大值减去最小值的结果大于num的个数。

大于

  这是最简单的一种情况了，分析：若一个子数组的最大最小值的差值大于某个给定值，则其包含这个子数组的子数组也满足给定的要求。所以关键在于如何快速找到最大最小值，排序尽管方便，却效率不高。

单调栈

  子数组的头从数组头开始i = 0，子数组的尾巴从子数组的头 + 1 开始，即j = i + 1，将子数组的全部下标依次进入单调栈（使用下标是为了方便计算个数），维持一个递增单调栈：
若当前比较的数小于栈尾，那么和栈头比较，若小于栈头，则替换栈头，若大于栈尾，则入栈
每次入栈或者替换都要计算栈头栈尾差值, 若差值大于给定num，那么包含这个子数组的数组也满足条件，可用下标计算个数
给出粗略代码：

import sys
def fuck(arr,num):
    count = 0
    for i in range(len(arr)):
        queen = []
        queen.append(i)
        for j in range(i+1,len(arr)):
            # print(i, j)
            if len(queen) == 0 or arr[queen[-1]] < arr[j]:
                queen.append(j)
                if arr[j] - arr[queen[0]] > num:
                    count += len(arr) - j
                    break
            elif arr[queen[-1]] > arr[j]:
                if arr[queen[-1]] - arr[j] > num:
                    count += len(arr) - j
                    break
    print(count)

                     
if __name__ == '__main__':
    input_arr= [int(x) for x in sys.stdin.readline().strip().split(" ")]
    input_num = int(sys.stdin.readline().strip())
    fuck(input_arr,input_num)

考虑是否能优化？？？

• 单调栈多余，就只用两个临时变量就可以了minimum 和 maximum
• 当i + 1 之后，仍然需要重新计算maximum 和 minimum，是否应该维持双端队列（同时具有单调栈的特性）来减少多余的计算，在代码queen重置之前，比较旧的 arr[i] 值是否是最小值或者最大值，若是最小值，那就将左端退出，并且接着右端（栈尾）存储的下标继续计算，直到找到或者找不到。若是最大值，将右端推出，接着左端（栈头）存储的下标继续计算。

等于

类似于以上，只不过不能用下标计算数量了。

小于

  双端队列的应用，