LeetCode每日一题系列

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

文章目录

• LeetCode每日一题系列
• 题目
• 示例
• 思路
• 题解

题目

给你一个整数数组 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,0for i,s in enumerate(nums):# 更新index和tmpif s>right:index,tmp=i,0# 第一种情况elif s>=left:tmp=i-index# 第二种情况res+=tmpreturn res