问题描述
给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。
求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数
例子
image.png
思路
1 暴力破解，使用两重循环遍历每一个子数组，判断子数组的最大值是否满足条件。
class Solution:
def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
n=len(A)
res=0
for i in range(n):
for j in range(i+1,n+1):
x=max(A[i:j])
if x>=L and x<=R:
res+=1
return res
3 求出子数组最大值<L的所有子数组的个数x1，和求出数组最大值<=R的子数组的个数x2。
然后返回 x2-x1
class Solution:
def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
def count(n):
ans = cur = 0
for x in A:
cur = cur+1 if x <= n else 0
ans += cur
return ans
return (count(R)-count(L-1))
2 在暴力破解的基础上，在第二重循环时记录子数组的最大值。
class Solution:
def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
n=len(A)
res=0
for i in range(n):
m=0
for j in range(i+1,n+1):
if A[j-1]>m:
m=A[j-1]
if m>R:
break
if m<L:
continue
res+=1
return res
来源：力扣
