Re: [閒聊] 每日leetcode

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

1014. Best Sightseeing Pair

思路:

我一開始是用max_heap

後來發現有O(n)的方式

假設max_j、max_i是最大pair中的j、i

那max_i就會是0~(max_j-1)中 (values[i]+i)為最大的i

所以就去遍歷values

並且維護最大的values[i]+i

ans= max(ans , 最大的(values[i]+i) + values[j]-j)

這樣就可以得到答案了

golang code :

func maxScoreSightseeingPair(values []int) int {
        ans, n, l := math.MinInt64, len(values), 0
        for i := 1; i < n; i++ {
                ans = max(ans, values[l]+l+values[i]-i)
                if values[i]+i > values[l]+l {
                        l = i
                }
        }
        return ans
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.171 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1735311020.A.7E4.html
推 SecondRun: 別捲了