Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- 子数组的取值范围
- Description
- 给定数组arr和整数num,求arr的连续子数组中满足:
- 其最大值减去最小值的结果大于num的个数。请实现一
- 个时间复杂度为O(length(arr))的算法。
- Input
- 输入的第一行为数组,每一个数用空格隔开,第二行为num。
- Output
- 输出一个值。
- Sample Input 1
- 3 6 4 3 2
- 2
- Sample Output 1
- 6
- '''
- #这里复杂度不是O(lengh(arr))
- def subArr(arr,num):
- n = 0
- for i in range(len(arr)):
- if i == len(arr) - 1:
- break
- for j in range(i+1,len(arr)):
- if max(arr[i:j+1])-min(arr[i:j+1]) > num:
- n +=1
- return n
- arr = list(map(int,input().split()))
- num = int(input())
- print(subArr(arr,num))
Add Comment
Please, Sign In to add comment