Re: [閒聊] 每日leetcode
2779. Maximum Beauty of an Array After Applying Operation
跟
3347. Maximum Frequency of an Element After Performing Operations II
3346. Maximum Frequency of an Element After Performing Operations I
這兩題很像
基本上改一下就可以了
思路:
(1)sliding windows
3個指標L1、L2、R
L2要滿足nums[i]-nums[L2]<=2*k
L1要滿足nums[i]-nums[L1]<=k
R要滿足nums[R]-nums[i]>k
就這樣維護idx-L2+1、R-L1的最大值就是答案
不過這樣很慢就是了
(2)
找到nums裡的最大值maxnum
建立一個長度為maxnum+2的矩陣arr
接著遍歷nums
把arr[nums[i]-k]++
arr[nums[i]+k+1]--
接著再去遍歷arr
用cnt+=arr[idx]
並記錄cnt的最大值就是答案
golang code
func maximumBeauty(nums []int, k int) int {
m := slices.Max(nums)
rec := make([]int, m+2)
for _, val := range nums {
rec[max(val-k, 0)]++
rec[min(val+k+1, m+1)]--
}
cnt, ans := 0, 0
for _, val := range rec {
cnt += val
ans = max(ans, cnt)
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.123 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1733920306.A.DC9.html
推
12/11 21:17,
1年前
, 1F
12/11 21:17, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1197 之 1554 篇)：