LeetCode每日一题——795. 区间子数组个数

LeetCode每日一题系列

题目：828. 统计子串中的唯一字符
难度：困难

---

---

题目

给你一个整数数组 nums 和两个整数：left 及 right 。找出 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

思路

一次遍历模拟即可

• index表示上一次遇到的大于给定区域的值的下标，意味着该下标之后的都是符合要求的坐标
• tmp表示上一个以给定区域值为最后一个元素的子数组个数
• 遍历数组，遇到元素nums[i]>right的更新tmp和index
• 遇到元素nums[i]<=right的又分为两种情况
  （1）nums[i]>=left，说明该元素在给定区域内，那么从上一个index开始以任意元素开头到nums[i]结束都符合条件
  （2）nums[i]

题解

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        res,index,tmp=0,-1,0
        for i,s in enumerate(nums):
        	# 更新index和tmp
            if s>right:
                index,tmp=i,0
            # 第一种情况
            elif s>=left:
                tmp=i-index
           	# 第二种情况
            res+=tmp
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13