问题描述
给你一个整数数组 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;
}
};
标签:tmp,满足条件,795,right,nums,力扣,数组,leetcode,left
From: https://www.cnblogs.com/greatestchen/p/16923573.html