首页 > 其他分享 >力扣 leetcode 795. 区间子数组个数

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

时间:2022-11-24 21:56:03浏览次数:36  
标签:tmp 满足条件 795 right nums 力扣 数组 leetcode left

问题描述

给你一个整数数组 nums 和两个整数:leftright 。找出 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

相关文章

  • 795. 区间子数组个数
    795.区间子数组个数classSolution{publicintnumSubarrayBoundedMax(int[]nums,intleft,intright){return(int)(cal(nums,right)-cal(nums,......
  • 力扣202 快乐数
    题目:编写一个算法来判断一个数n是不是快乐数。「快乐数」 定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这......
  • leetcode1552
    两球之间的磁力Category Difficulty Likes Dislikesalgorithms Medium(51.48%) 122 -TagsUnknownCompaniesUnknown在代号为C-137的地球上,Rick发现如果他将两个......
  • #yyds干货盘点# LeetCode 腾讯精选练习 50 题:Nim 游戏
    题目:你和你的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头。你们轮流进行自己的回合, 你作为先手 。每一回合,轮到的人拿掉 1-3块石头。拿掉最后一块石头的人就是获胜者......
  • 力扣349 两个数组的交集
    题目:给定两个数组 nums1 和 nums2,返回它们的交集 。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。示例:输入:nums1=[1,2,2,1],nums......
  • 795. 区间子数组个数
    795.区间子数组个数给你一个整数数组nums和两个整数:left及right。找出nums中连续、非空且其中最大元素在范围 [left,right]内的子数组,并返回满足条件的子数组......
  • 力扣81(java&python)-搜索旋转排序数组 II(中等)
    题目:已知存在一个按非降序排列的整数数组nums,数组中的值不必互不相同。在传递给函数之前,nums在预先未知的某个下标k(0<=k<nums.length)上进行了旋转,使数组变为[......
  • [leetcode每日一题]11.24
    ​​795.区间子数组个数​​给你一个整数数组 ​​nums​​ 和两个整数:​​left​​ 及 ​​right​​ 。找出 ​​nums​​ 中连续、非空且其中最大元素在范围 ​......
  • [LeetCode] 795. Number of Subarrays with Bounded Maximum
    Givenanintegerarray nums andtwointegers left and right,return thenumberofcontiguousnon-empty subarrays suchthatthevalueofthemaximumarr......
  • 力扣 leetcode 3. 无重复字符的最长子串
    题目描述给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。提示:0<=s.length<=5*104s由英文字母、数字、符号和空格组成示例示例1:输入:s=......