问题描述
给你一个整数数组 nums
和两个整数:left
及 right
。找出 nums
中连续、非空且其中最大元素在范围 [left, right]
内的子数组,并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit
整数范围。
提示:
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= left <= right <= 10^9
示例
示例1:
输入:nums = [2,1,4,3], left = 2, right = 3
输出:3
解释:满足条件的三个子数组:[2], [2, 1], [3]
示例2:
输入:nums = [2,9,2,5,6], left = 2, right = 8
输出:7
解释:满足条件的七个子数组:[2], [2], [5], [6], [2, 5], [5, 6], [2, 5, 6]
解体思路
本题中比较关键的是,找出数组中所有元素小于right
的连续子数组。然后再计算子数组中满足条件的子数组的个数。
例如,nums = [2, 9, 2, 5, 6], left = 3, right = 8
,其中所有元素都小于right
的连续子数组有:[2], [2, 5, 6]
。第一个子数组中满足条件的子数组有且只有一个,第二个子数组中,满足条件的子数组个数可以按如下方式计算:
- 遍历子数组中每一个元素,如果该元素大于等于
left
,则该元素可以与后面的所有元素组成满足条件的子数组。 - 如果该元素小于
left
,则它可以与后面的第一个大于等于left
的元素共同组成满足条件的子数组。
下面看一个具体的例子:
nums = [1, 2, 3, 4, 6], left = 3, right = 5
。我们先遍历nums
,发现所有元素小于right
的子数组为:sub = [1, 2, 3, 4]
。计算包含nums[i]
的子数组的个数:
i = 0
时,nums[i] < left
,记录此时小于left
的元素的个数tmp = 1
i = 1
时,nums[i] < left
,记录此时小于left
的元素的个数tmp = 2
i = 2
时,nums[i] = left
,满足条件的子数组个数为:cnt = sub.size() - i
,此外,nums[0]
和nums[1]
也可以与num[2]
组成满足条件的子数组,个数也是sub.size() - i
,令tmp = 0
i = 3
时,nums[i] > left
,满足条件的子数组个数为:cnt = sub.size() - i
因此,总的满足条件的子数组个数为:total = (sub.size() - 2) * 3 + (sub.size() - 3) = 7
。
按这个思路完成本题,具体代码为:
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int cnt = 0;
int start_index = 0;
int tmp = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] > right){
if(nums[start_index] <= right){
tmp = 0;
for(int j = start_index; j < i; j++){
if(nums[j] >= left){
cnt = tmp == 0 ? (cnt + i - j) : (cnt + (i - j) * (tmp + 1));
tmp = 0;
}
else{
tmp += 1;
}
}
}
start_index = i + 1;
}
}
if(start_index < nums.size()){
tmp = 0;
for(int i = start_index; i < nums.size(); i++){
if(nums[i] >= left){
cnt = tmp == 0 ? (cnt + nums.size() - i) : (cnt + (nums.size() - i) * (tmp + 1));
tmp = 0;
}
else{
tmp += 1;
}
}
}
return cnt;
}
};
原文地址:http://www.cnblogs.com/greatestchen/p/16923573.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性