标签:795 right 数组 int 个数 last1 端点 last2
题目描述
给一个数组,再给一个值的范围[l, r],
问最大值在[l, r]之间的子数组有多少个?
基本分析
- 如果枚举子数组的右端点i,会有几种情况?(1)arr[i] > right; (left <= arr[i] <= right; (3)arr[i] < left
- 假如枚举到右端点i,左端点怎么考虑?(1)的情况,这个子数组不满足,可以跳过;(2)的情况i可以是一个最近的左端点,只需要找到最远的左端点i就行。分两种情况,前面没有>right的索引,i就是0;前面有>right的索引,i就是索引+1;(3)的情况,自己不能当左端点,除了找最远的左端点以外,还要找最近的左端点i’,可选的左端点个数是i' - i
- 怎么实现以上逻辑?用两个指针last1表示最近的左端点位置;last2表示最近的>right的位置。对枚举到的每个值,当last1存在的时候,表示有左端点存在,就可以累加结果
代码
class Solution:
def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
last1 = last2 = -1
ans = 0
for i, x in enumerate(nums):
if left <= x <= right:
last1 = i
elif x > right:
last2 = i
last1 = -1
if last1 != -1:
ans += last1 - last2
return ans
总结
- 枚举右端点,右端点可以保证子数组不同
- 个数取决于可选的左端点范围,这里用last1和last2来维护
基本分析
- 怎么用计数的角度考虑?(1)找<= right的区间个数(2)找<=left-1的区间个数;(3)求差
- 怎么统计<=x的区间个数?如果长度是l,个数就是1+2+3+...+l,碰到不满足的重新计数。
代码
class Solution:
def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
def cal(x):
ans = 0
cnt = 0
for num in nums:
if num <= x:
cnt += 1
else:
cnt = 0
ans += cnt
return ans
return cal(right) - cal(left - 1)
总结
- 利用题目的要求,压缩每个数字的含义,使其变为简单的0、1和2
- 利用容斥的思想,使用计数解决
待补充
基本分析
- xxx
代码
总结
- xxx
标签:795,
right,
数组,
int,
个数,
last1,
端点,
last2
From: https://www.cnblogs.com/zk-icewall/p/17288307.html