美文网首页
795. 区间子数组的个数(Python)

795. 区间子数组的个数(Python)

作者: 玖月晴 | 来源:发表于2021-01-26 20:21 被阅读0次

难度:★★★☆☆
类型:数组
方法:逻辑

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

给定一个元素都是正整数的数组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] 都是整数,范围在 [0, 10^9]。
数组 A 的长度范围在[1, 50000]。

解答

这道题不难,摘一下官网解答。我们定义一个函数count,函数的输入是一个数字,函数的输出是数组A中,最大值不超过该数字的子数组的个数。

既然题目要求我们找出的子数组中的最大值是在一个区间(L,R),那么可以计算出count(R)和count(L-1),然后做减法即可。这里需要注意,由于编码规则和题目要求缘故,下界需要是L-1。另外需要注意的是,题目限制了子数组的最大值,而没有对最小值进行限制(如果还限制最小值不小于某个阈值,那么这道题更简单了,直接筛选求阶乘就好)。

class Solution(object):
    def numSubarrayBoundedMax(self, A, L, R):
        def count(bound):
            ans = cur = 0
            for x in A:
                cur = cur + 1 if x <= bound else 0
                ans += cur
            return ans
        return count(R) - count(L - 1)

如有疑问或建议,欢迎评论区留言~

有关更多力扣中等题的python解决方案,请移步力扣中等题解析

相关文章

  • 795. 区间子数组的个数(Python)

    难度:★★★☆☆类型:数组方法:逻辑 力扣链接请移步本题传送门[https://leetcode-cn.com/p...

  • 795. 区间子数组个数

    题目: 给你一个整数数组 nums 和两个整数:left 及 right 。找出 nums 中连续、非空且其中最大...

  • 最小区间问题

    题目描述:k个有序的数组,找到最小的区间范围使得这k个数组中,每个数组至少有一个数字在这个区间范围内。比如: 数组...

  • 力扣 239 滑动窗口最大值

    题意:给定一个数组和一个区间,在数组上,从头开始移动区间,返回移动过程中区间的最大值 思路:遍历数组,用双向队列来...

  • 桶排序

    有n个数,在区间1-m,初始化一个数组,大小为m,记为array[m]。把n个数逐个放入数组,下标与之对应,arr...

  • 树状数组与离散化

    用途 树状数组主要用来求解前缀和、区间和、逆序对、区间和的个数和相关求个数的问题等等问题,最重要的是要考虑怎么将题...

  • js实现二维数组中找出最大的一个,并返回数组

    现在给你一个数组,这个数组中包含了数字的子数组。 请编写程序,从数组的每一个子数组中返回其最大的那个数。目标数...

  • 今日头条 2018 AI Camp 6 月 2 日在线笔试编程题

    题目 给出一个长度为 n 的数组,请找出在所有连续区间 中,区间和最大同时这个区间 0 的个数小于等于 3 个,输...

  • Leetcode.56.Merge Intervals

    题目 给定一个二维数组, 数组里面包含的子数组都是一个闭区间, 合并这些区间. 思路 先排序, 然后依次合并. 关...

  • 1.2 数组连续递增区间

    记某面试题目:输入为正整数数组,找出排好序的数组的所有连续区间, 如果该连续空间只有一个数字,将该数字放入一个数组...

网友评论

      本文标题:795. 区间子数组的个数(Python)

      本文链接:https://www.haomeiwen.com/subject/oieqzktx.html