Medium

题目描述

给你一个整数数组 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^5
  • 0 <= start[i] <= 10^9
  • 0 <= d <= 10^9

提示：

  • 这里可以使用二分查找吗？
  • 假设答案是 x。我们可以通过排序 start 来找到一个有效的整数配置，第一个整数应该是 start[0]，然后每个后续整数应该是 [start[i], start[i] + d] 中大于 last_chosen_value + x 的最小整数。
  • 对 x 进行二分查找

解题思路

解题思路

这道题的核心思想是使用二分查找 + 贪心策略来解决。

首先分析问题：我们要在每个区间内选择一个数，使得所选数字之间的最小差值最大。这是一个典型的最大化最小值问题，可以用二分查找来解决。

核心观察：

  1. 如果我们固定最小差值为 x，那么可以贪心地验证是否能选出满足条件的数字
  2. 为了让相邻数字的差值尽可能大，我们应该对区间起点进行排序
  3. 贪心策略：选择第一个区间的起点，然后在后续每个区间中选择满足最小差值要求的最小数字

算法步骤：

  1. 对 start 数组排序
  2. 二分查找答案范围：左边界为 0，右边界为区间总跨度
  3. 对于每个候选答案 mid，检查是否能在每个区间内选择数字使得最小差值至少为 mid
  4. 验证函数使用贪心策略：从第一个区间开始，每次选择满足条件的最小数字

贪心验证的正确性： 如果存在一个有效方案，那么贪心选择（每次选最小的满足条件的数）一定也能得到有效方案，因为选择更小的数不会影响后续选择的可行性。

时间复杂度：O(n log n + n log(max_range))，其中排序需要 O(n log n)，二分查找需要 O(log(max_range))，每次验证需要 O(n)。

代码实现

class Solution {
public:
    int maxPossibleScore(vector<int>& start, int d) {
        sort(start.begin(), start.end());
        
        long long left = 0, right = (long long)start.back() + d - start[0];
        long long result = 0;
        
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            
            if (canAchieveScore(start, d, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
private:
    bool canAchieveScore(vector<int>& start, int d, long long minDiff) {
        long long lastChosen = start[0];
        
        for (int i = 1; i < start.size(); i++) {
            long long nextMin = lastChosen + minDiff;
            long long intervalStart = start[i];
            long long intervalEnd = (long long)start[i] + d;
            
            if (nextMin > intervalEnd) {
                return false;
            }
            
            lastChosen = max(nextMin, intervalStart);
        }
        
        return true;
    }
};

class Solution:
    def maxPossibleScore(self, start: List[int], d: int) -> int:
        start.sort()
        
        left, right = 0, start[-1] + d - start[0]
        result = 0
        
        while left <= right:
            mid = (left + right) // 2
            
            if self.canAchieveScore(start, d, mid):
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result
    
    def canAchieveScore(self, start: List[int], d: int, minDiff: int) -> bool:
        lastChosen = start[0]
        
        for i in range(1, len(start)):
            nextMin = lastChosen + minDiff
            intervalStart = start[i]
            intervalEnd = start[i] + d
            
            if nextMin > intervalEnd:
                return False
            
            lastChosen = max(nextMin, intervalStart)
        
        return True

public class Solution {
    public int MaxPossibleScore(int[] start, int d) {
        Array.Sort(start);
        
        long left = 0, right = (long)start[start.Length - 1] + d - start[0];
        long result = 0;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            
            if (CanAchieveScore(start, d, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return (int)result;
    }
    
    private bool CanAchieveScore(int[] start, int d, long minDiff) {
        long lastChosen = start[0];
        
        for (int i = 1; i < start.Length; i++) {
            long nextMin = lastChosen + minDiff;
            long intervalStart = start[i];
            long intervalEnd = (long)start[i] + d;
            
            if (nextMin > intervalEnd) {
                return false;
            }
            
            lastChosen = Math.Max(nextMin, intervalStart);
        }
        
        return true;
    }
}

var maxPossibleScore = function(start, d) {
    start.sort((a, b) => a - b);
    
    let left = 0, right = start[start.length - 1] + d - start[0];
    let result = 0;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        if (canAchieveScore(start, d, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};

function canAchieveScore(start, d, minDiff) {
    let lastChosen = start[0];
    
    for (let i = 1; i < start.length; i++) {
        let nextMin = lastChosen + minDiff;
        let intervalStart = start[i];
        let intervalEnd = start[i] + d;
        
        if (nextMin > intervalEnd) {
            return false;
        }
        
        lastChosen = Math.max(nextMin, intervalStart);
    }
    
    return true;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n + n log(max_range))排序 O(n log n)，二分查找 O(log(max_range))，每次验证 O(n)
空间复杂度O(1)只使用常数额外空间，排序为原地排序

相关题目