1014. Best Sightseeing Pair

Problem

You are given an integer array values where values[i] represents the value of the iᵗʰ sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.

The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

https://leetcode.com/problems/best-sightseeing-pair/

Example 1:

Input: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

Example 2:

Input: values = [1,2]
Output: 2

Constraints:

• 2 <= values.length <= 5 * 10⁴
• 1 <= values[i] <= 1000

Test Cases

1
2

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import pytest

from solution import Solution


@pytest.mark.parametrize('values, expected', [
    ([8,1,5,2,6], 11),
    ([1,2], 2),

    ([1,3,5], 7),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, values, expected):
    assert sol.maxScoreSightseeingPair(values) == expected

Thoughts

把分数的算式改写为 (values[i] + i) + (values[j] - j)。对于任何 j，想要分数最高，需要与它左边 values[i] + i 最大的那个结对。从左向右扫描数组的时候，可以记录已知的 values[i] + i 的最大值。最后对所有的 j，取结对分数最大的即可。

时间复杂度 O(n)，空间复杂度 O(1)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13

from math import inf


class Solution:
    def maxScoreSightseeingPair(self, values: list[int]) -> int:
        max2 = lambda a, b: a if a >= b else b
        max_score = -inf
        max_left = values[0]
        for j in range(1, len(values)):
            max_score = max2(max_score, max_left + values[j] - j)
            max_left = max2(max_left, values[j] + j)

        return max_score

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章