- 搜索
日期：2025/04/05 12:38来源：未知 人气：52
给定一个由正整数组成的数组A，以及两个正整数L和R（L <= R）。
返回（连续的非空）子数组的数量，以使该子数组中最大数组元素的值至少为L，至多为R。
示例：
输入：
A = [2，1，4，3]
L = 2
R = 3
输出：3
说明：有三个满足要求的子阵列：[2]，[2、1]，[3]。
Java解决方案
此问题的边界是每个元素的总和，而不是总和。很容易误解这个问题，因为有很多与总和有关的问题。
给定样本[2,1,4,3]中的数组，我们可以将其转换为数组[0,0,1,0]，这意味着如果元素在边界内，则为0。子数组的数量。
给定一个数组，子数组的总数遵循以下模式：
[0]-> 1
[0,0]-> 2 + 1（单元素子数组+ 2元素子数组）
[0,0,0]-> 3 + 2 + 1
[0,0,0,0]-> 4 + 3 + 2 + 1
因此，解决方案是R的countBelowBoundary-（L-1）的countBelowBoundary。
publicintnumSubarrayBoundedMax(int[] A, int L, int R) {
returncountBelowBoundary(A, R)-countBelowBoundary(A,L-1);}
publicintcountBelowBoundary(int[] A, int bound){
intcount = 0;
inttemp = 0;
for(inta: A){
if(a<=bound){
temp = temp +1;
count += temp;
}else{
temp = 0;
}
}
returncount;}
时间为O（N），空间为O（1）。
最后，开发这么多年我也总结了一套学习Java的资料与面试题，如果你在技术上面想提升自己的话，可以关注我，私信发送领取资料或者在评论区留下自己的联系方式，有时间记得帮我点下转发让跟多的人看到哦。
上一篇：哈希算法原理「Java实现」
下一篇：Java中大型集合的优化
