力扣 leetcode 795. 区间子数组个数()

问题描述

给你一个整数数组 和两个整数: 及 。找出 中连续、非空且其中最大元素在范围 内的子数组,并返回满足条件的子数组的个数。

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;
    }
};
————————

问题描述

给你一个整数数组 和两个整数: 及 。找出 中连续、非空且其中最大元素在范围 内的子数组,并返回满足条件的子数组的个数。

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;
    }
};