LeetCode 414场周赛

范围内整数的最大得分

题目描述：

给你一个整数数组 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

解题思路

1. 问题分析

给定 n 个区间 [start[i], start[i] + d]，你需要从每个区间中选取一个数，并最大化这些数之间的最小绝对差。

由于顺序不会影响结果，可以先将 start 数组进行排序。我们可以通过二分法来推导最大可能的最小绝对差 res。

2. 二分法

假设我们二分的中间值 res 代表选取数之间的最小绝对差。对于每个区间 [start[i], start[i] + d]，我们尝试选取一个数，使得与前一个数的差至少为 res。

将数组排序后，我们需要思路各个区间数字的选择，如果从总的来看的化太复杂，我们可以从就近的一两个区间来思考，我们可以假设上一个区间选择了数字x，那么第二区间至少是x+res，为什么直接加上res，因为res是min(a_i-a_j)，只要res存在自那么，x+res就是众多选择的一个，如果任意区间满足，那么res就是合法答案中的一个，我们只是取其中最大的一个。

• 如果当前区间无法满足这个 res，则说明 res 太大，应减少右边界。
• 如果当前区间可以满足这个 res，则说明可以尝试更大的 res，继续增大左边界。

3. 边界更新

• 左边界更新：如果当前区间的数满足 xi = max(xi-1 + res, start[i])，且 xi <= start[i] + d，则 res 可行，继续增大。
• 右边界更新：若选取的数超过了区间右端点，则 res 太大，减小右边界。

代码实现

import java.util.Arrays;

class Solution {
    public int maxPossibleScore(int[] start, int d) {
        // 先对 start 数组进行排序
        Arrays.sort(start);
        int left = 0;
        int n = start.length;
        // 计算右边界：从 start[0] 到 start[n-1] + d 的最大间隔除以 n-1
        int right = (start[n - 1] + d - start[0]) / (n - 1) + 1;

        // 使用二分法查找最大可能得分
        while (left + 1 < right) {
            int mid = left + ((right - left) >>> 1);
            if (check(start, d, mid)) {
                left = mid; // mid 可行，尝试更大的得分
            } else {
                right = mid; // mid 不可行，缩小范围
            }
        }
        return left; // 返回最大得分
    }

    // 检查当前得分 res 是否可行
    public boolean check(int[] start, int d, int res) {
        long x = Integer.MIN_VALUE; // 记录前一个选取的数
        for (int num : start) {
            // 当前区间能否选到合适的数
            if (x + res <= num + d) {
                x = Math.max(x + res, num); // 选出符合条件的数
            } else {
                return false; // 如果无法选取，说明 res 太大
            }
        }
        return true; // 如果所有区间都能满足条件，返回 true
    }
}

通过二分法进行最大得分的计算，我们将问题复杂度从 O(n^2) 降低到 O(n log(maxRange))，其中 maxRange 是区间的最大可能差值。

到达数组末尾的最大得分

给你一个长度为 n 的整数数组 nums。

你的目标是从下标 0 出发，到达下标 n - 1 处。每次你只能移动到 更大 的下标处。

从下标 i 跳到下标 j 的得分为 (j - i) * nums[i]。

请你返回你到达最后一个下标处能得到的 最大总得分。

示例

示例 1：

• 输入：nums = [1, 3, 1, 5]
• 输出：7
• 解释：
  一开始跳到下标 1 处，然后跳到最后一个下标处。总得分为 1 * 1 + 2 * 3 = 7。

示例 2：

• 输入：nums = [4, 3, 1, 3, 2]
• 输出：16
• 解释：
  直接跳到最后一个下标处。总得分为 4 * 4 = 16。

提示

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

解题思路

图片来源：LeetCode 题解 - Reach End of Array with Max Score【12†source】

    class Solution {
        public long findMaximumScore(List<Integer> nums) {
            int i = 0;
            int now = 0;
            long res = 0;
            while(i < nums.size()-1){
                if(nums.get(i)  > nums.get(now)){
                    res += (long) (i - now)*nums.get(now);
                    now = i;
                }
                i++;
            }
            res += (long)(nums.size()-1 - now)*nums.get(now);

            return res;
        }
    }