又是hard我要吐了
2444. Count Subarrays With Fixed Bounds
有一个array : nums、两个整数 : minK、maxK
请找出所有的subarray符合以下条件
1.subarray的最大值==maxK
2.subarray的最小值==minK
思路 :
用sliding windows
用maxid、minid分别纪录i跟j : nums[i]==maxK、nums[j]==minK
并用bound纪录a : nums[a]>maxK || nums[a]<minK
当a<min(maxid,minid)的时候符合条件的subarray就出现了
接着从max(maxid,minid)往后找直到找到 nums[b]>=maxK || nums[b]<=minK
那就可以用a、min(maxid,minid)、max(maxid,minid)、b这4个指标
找到a、b之间符合条件的subarray数量
接着就一直重复下去，就得到答案了
golang code :
func countSubarrays(nums []int, minK int, maxK int) int64 {
maxid := -1
minid := -1
bound := -1
nums=append(nums,maxK+1)
l, r, n := 0, 0, len(nums)
ans := 0
for r < n {
if nums[r] > maxK || nums[r] < minK {
bound = r
}
if nums[r] == maxK {
maxid = r
}
if nums[r] == minK {
minid = r
}
temp1 := max(maxid, minid)
temp2 := min(maxid, minid)
if bound < temp2 {
l = temp1
for l < n {
l++
if nums[l] >= maxK || nums[l] <= minK {
break
}
}
r = l
ans += (temp2 - bound) * (l - temp1)
} else {
r++
}
}
return int64(ans)
}