当前位置：首页 > ai >正文

统计定界子数组的数组

ai 2025/7/5 20:12:16

前言：看到这个题目的时候，只想着怎么暴力枚举右端点，结合线段树还是会超时，没找到很好的处理方法

在这里插入图片描述

超时代码

class Tree1:def __init__(self,n):self.t = [0]*(4*n)def update(self,o,l,r,index,va):if l==r:self.t[o] = vareturnmid = (l+r)//2if index<=mid:self.update(o*2,l,mid,index,va)else:self.update(o*2+1,mid+1,r,index,va)self.t[o] = max(self.t[o*2],self.t[o*2+1])def query(self,o,l,r,L,R):if L<=l and r <=R:return self.t[o]tmp = 0mid = (l+r)//2if mid>=L:tmp = max(tmp,self.query(o*2,l,mid,L,R))if R>mid:tmp = max(tmp,self.query(o*2+1,mid+1,r,L,R))return tmp
class Tree2:def __init__(self,n):self.t = [1000006]*(4*n)def update(self,o,l,r,index,va):if l==r:self.t[o] = vareturnmid = (l+r)//2if index<=mid:self.update(o*2,l,mid,index,va)else:self.update(o*2+1,mid+1,r,index,va)self.t[o] = min(self.t[o*2],self.t[o*2+1])def query(self,o,l,r,L,R):if L<=l and r <=R:return self.t[o]tmp = 1000006mid = (l+r)//2if mid>=L:tmp = min(tmp,self.query(o*2,l,mid,L,R))if R>mid:tmp = min(tmp,self.query(o*2+1,mid+1,r,L,R))return tmpclass Solution:def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:le = 0n = len(nums)big = Tree1(n)xiao = Tree2(n)le = 0ans = 0pre = 0for i,va in enumerate(nums):big.update(1,0,n-1,i,va)xiao.update(1,0,n-1,i,va)if va>maxK or va <minK:le = i+1pre = 0continueif pre!=0 and minK < va <maxK:ans += precontinuepre = 0for j in range(le,i+1):tmpxiao = xiao.query(1,0,n-1,j,i)tmpbig = big.query(1,0,n-1,j,i)# print("xiao",j,i,tmpxiao)# print("big",j,i,tmpbig)if tmpxiao==minK and tmpbig ==maxK:pre += 1else:breakans += prereturn ans

看了题解才发现是自己思维狭隘了，这个题目我每次遇到小于minK和大于maxK的值重新计数是对的，但是可以有更加优化的方法

class Solution:def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:ans = 0min_i = max_i = i0 = -1for i, x in enumerate(nums):if x == minK:min_i = i  # 最近的 minK 位置if x == maxK:max_i = i  # 最近的 maxK 位置if not minK <= x <= maxK:i0 = i  # 子数组不能包含 nums[i0]ans += max(min(min_i, max_i) - i0, 0)return ans