Re: [閒聊] 每日leetcode
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
推
12/27 22:52,
11月前
, 1F
12/27 22:52, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1225 之 1554 篇)：