Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

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
推 sixB: 原來可以slide 好酷