Re: [閒聊] 每日leetcode已回收
又是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)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.141.243.109 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1711867002.A.BAB.html
→
03/31 14:40,
1年前
, 1F
03/31 14:40, 1F
→
03/31 14:50,
1年前
, 2F
03/31 14:50, 2F
推
03/31 14:55,
1年前
, 3F
03/31 14:55, 3F
※ 編輯: JIWP (223.141.243.109 臺灣), 03/31/2024 14:55:40
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 82 之 1548 篇)：