又是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)
}