代码编织梦想

题目

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

生成的测试用例保证结果符合 32-bit 整数范围。

 

示例 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

 

提示:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= left <= right <= 109

分析

关键词子数组,看到这个可以想到二层循环暴力,最坏的情况要计算10^10次,必定超时,这里说一个子数组的性质。

在没有条件的限制下,一个长度为N数组的子数组数量是 1 + 2 + … + N,也就是说一次循环就可以统计所有的子数组,比如:长度为4的数组,子数组的数量应该是10,既1 + 2 + 3 + 4 = 10,代表着当前下标(ci)到下标0之间子数组元素的数量。

根据题意,子数组内的最大值必须在[left, right]之内,既left <= max(子数组) <= right,利用上面子数组的性质进行结合:
核心思路我们就只要确定两个坐标,i0和i1,然后有i0 - i1,i0就是子数组元素最大值在[left, right]范围内的下标,i1其实就是最后一个最大值大于right的下标。i0 - i1就是我们上面说的性质

代码

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int ans = 0, i0 = 0, i1 = -1;
        int N = nums.length;
        boolean flat = false;
        for (int i = 0; i < N; ++i) {
            if (nums[i] >= left && nums[i] <= right) {
                i0 = i;
                flat = true;
            } 
            if (nums[i] > right) {
                i1 = i;
                flat = false;
            }
            if (flat) {
                ans += i0 - i1;
            }
        }
        return ans;
    }
}

暴力

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            int max = -1;
            for (int j = i; j < nums.length; ++j) {
                if (nums[j] > max) max = nums[j];
                if (max <= right && max >= left) ans++;
            }
        }
        return ans;
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_45716444/article/details/128012685

leetcode 795. 区间子数组个数(c++、python)_我很忙2010的博客-爱代码爱编程_统计数组落在子区间的个数

给定一个元素都是正整数的数组A ,正整数 L 以及 R (L <= R)。 求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。 例如 : 输入: A = [2, 1, 4, 3] L = 2 R = 3 输出: 3 解释: 满足条件的子数组: [2], [2, 1], [3]. 注意: L, R  和 A[i] 都是整数,

leetcode:795. 区间子数组个数_cold_sun_的博客-爱代码爱编程

题目描述: 给定一个元素都是正整数的数组A ,正整数 L 以及 R (L <= R)。 求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。   输入输出: 输入: A = [2, 1, 4, 3] L = 2 R = 3 输出: 3 解释: 满足条件的子数组: [2], [2, 1], [3]. 注意:     L, R

leetcode 795. 区间子数组个数_head_hard的博客-爱代码爱编程

给定一个元素都是正整数的数组A ,正整数 L 以及 R (L <= R)。 求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。 例如 : 输入:  A = [2, 1, 4, 3] L = 2 R = 3 输出: 3 解释: 满足条件的子数组: [2], [2, 1], [3]. 查找满足小于等于R,大于等于L的字数组可以转化为

LeetCode 刷题系列 795. 区间子数组个数-爱代码爱编程

题目: 给定一个元素都是正整数的数组A ,正整数 L 以及 R (L <= R)。 求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。 例如 : 输入:  A = [2, 1, 4, 3] L = 2 R = 3 输出: 3 解释: 满足条件的子数组: [2], [2, 1], [3]. 注意: L, R  和 A[i] 都是

Leecode 795. 区间子数组个数 (双指针+计数技巧)-爱代码爱编程

将问题转化为求最大值不超过right的子数组的个数减去最大值不超过left-1的个数,就是最大值范围在left和right之间子数组的个数。 而最大值不超过k的子数组的个数,可以通过双指针分段很好的解决。 using LL = long long; class Solution { public: int numSubarrayBoun

leetcode_区间问题_中等_795.区间子数组个数_小城老街的博客-爱代码爱编程

目录 1.题目2.思路3.代码实现(Java) 1.题目 给你一个整数数组 nums 和两个整数:left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的

c语言百日千题系列之《忘情水题》第一日_会敲代码的史蒂夫.的博客-爱代码爱编程

目录 绪论 1.最大数位置 2.与指定数字相同的数的个数 3.蓝桥杯2013年第四届真题-核桃的数量 4.求所给范围内水仙花数并排列 5.最大值和最小值的差 6.计算书费 7.角谷猜想 8. 最高的分数 9.年龄与疾病 10.-百钱百鸡问题 绪论       本文是C语言百日千题系列《忘情水题》的第一篇专栏文章,主要为初学

leetcode 795. 区间子数组个数_小张刷题日记的博客-爱代码爱编程

好久没更新啦~最近忙着课题呢 研究生生活感觉有点子没意思 多学习总结 热爱生活!!芜湖~! 题目描述: 给你一个整数数组 nums 和两个整数:left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组,并返回满足条件的子数组的个数。 生成的测试用例保证结果符合 32-bit 整数范围。 题

leetcode 795. 区间子数组个数_ky0ma的博客-爱代码爱编程

模拟,计算贡献 以当前数字nums[i]为右端点,统计可能分为子数组的左端点。 nums[i]有三种情况: 1.大于right,此时不能作为右段点。 2.在[left, right]区间内此时可以作为右端点,此时可以分为的子

leetcode-795. 区间子数组个数【双指针】_旋转的油纸伞的博客-爱代码爱编程

LeetCode-795. 区间子数组个数【双指针】 题目描述:解题思路一:一次遍历。左指针维护大于right的下标,右指针维护大于left的下标。解题思路二:0解题思路三:0 题目描述: 给你一个整数数组

2022大厂面试秘籍java岗:中间件+算法+http+线程+虚拟机+分布式_啊码的博客-爱代码爱编程

前言 很多朋友对面试不够了解,不知道如何准备,对面试环节的设置以及目的不够了解,因此成功率不高。通常情况下校招生面试的成功率低于1%,而社招的面试成功率也低于5%,所以对于候选人一定要知道设立面试的初衷以及每个环节的意义,

【csdn竞赛】第十期解题报告_icehomegre的博客-爱代码爱编程

文章目录 感想关于自己关于平台 第一题 (难度:入门)题目描述100分做法 第二题 (难度:简单)题目描述100分做法 第三题 (难度:中等/困难)题目描述100分做法1(对应中等)10