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
}