范围内整数的最大得分

3281. 范围内整数的最大得分

给你一个整数数组 start 和一个整数 d，代表 n 个区间 [start[i], start[i] + d]。

你需要选择 n 个整数，其中第 i 个整数必须属于第 i 个区间。所选整数的得分定义为所选整数两两之间的最小绝对差。

返回所选整数的 最大可能得分 。

示例 1：

输入： start = [6,0,3], d = 2

输出： 4

解释：

可以选择整数 8, 0 和 4 获得最大可能得分，得分为 min(|8 - 0|, |8 - 4|, |0 - 4|)，等于 4。

示例 2：

输入： start = [2,6,13,13], d = 5

输出： 5

解释：

可以选择整数 2, 7, 13 和 18 获得最大可能得分，得分为 min(|2 - 7|, |2 - 13|, |2 - 18|, |7 - 13|, |7 - 18|, |13 - 18|)，等于 5。

提示：

2 <= start.length <= 10⁵
0 <= start[i] <= 10⁹
0 <= d <= 10⁹

相似题目

找出第 K 小的数对距离

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxPossibleScore(vector<int>& start, int d) { } };

python3 解法, 执行用时: 2266 ms, 内存消耗: 31.4 MB, 提交时间: 2024-09-19 09:50:41

class Solution:
    def maxPossibleScore(self, start: List[int], d: int) -> int:
        start.sort()

        def check(score: int) -> bool:
            x = -inf
            for s in start:
                x = max(x + score, s)  # x 必须 >= 区间左端点 s
                if x > s + d:
                    return False
            return True

        left, right = 0, (start[-1] + d - start[0]) // (len(start) - 1) + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left
        

    # 使用bisect库
    def maxPossibleScore2(self, start: List[int], d: int) -> int:
        start.sort()
        # 二分最小的不满足要求的 score+1，最终得到的答案就是最大的满足要求的 score
        def check(score: int) -> bool:
            score += 1
            x = -inf
            for s in start:
                x = max(x + score, s)  # x 必须 >= 区间左端点 s
                if x > s + d:
                    return True
            return False
        return bisect_left(range((start[-1] + d - start[0]) // (len(start) - 1)), True, key=check)

java 解法, 执行用时: 57 ms, 内存消耗: 57.2 MB, 提交时间: 2024-09-19 09:49:56

class Solution {
    public int maxPossibleScore(int[] start, int d) {
        Arrays.sort(start);
        int n = start.length;
        int left = 0;
        int right = (start[n - 1] + d - start[0]) / (n - 1) + 1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(start, d, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check(int[] start, int d, int score) {
        long x = Long.MIN_VALUE;
        for (int s : start) {
            x = Math.max(x + score, s); // x 必须 >= 区间左端点 s
            if (x > s + d) {
                return false;
            }
        }
        return true;
    }
}

cpp 解法, 执行用时: 239 ms, 内存消耗: 105.9 MB, 提交时间: 2024-09-19 09:49:47

class Solution {
public:
    int maxPossibleScore(vector<int>& start, int d) {
        ranges::sort(start);

        auto check = [&](int score) -> bool {
            long long x = LLONG_MIN;
            for (int s : start) {
                x = max(x + score, (long long) s); // x 必须 >= 区间左端点 s
                if (x > s + d) {
                    return false;
                }
            }
            return true;
        };

        int left = 0, right = (start.back() + d - start[0]) / (start.size() - 1) + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};

golang 解法, 执行用时: 172 ms, 内存消耗: 9.7 MB, 提交时间: 2024-09-19 09:49:33

func maxPossibleScore(start []int, d int) int {
	slices.Sort(start) // 先排序，asc
	n := len(start)
	// 二分最小的不满足要求的 score+1，最终得到的答案就是最大的满足要求的 score
	return sort.Search((start[n-1]+d-start[0])/(n-1), func(score int) bool {
		score++
		x := math.MinInt
		for _, s := range start {
			x = max(x+score, s) // x 必须 >= 区间左端点 s
			if x > s+d {
				return true
			}
		}
		return false
	})
}

上一题

下一题

详情