3281. Maximize Score of Numbers in Ranges - Medium

前往題目

想法

• 毫無頭緒，只覺得應該要用binary search來做，但無從下手

思路

即便思考許久，也參考網路上解答，但還是沒有完全理解這題

1. Binary serach搜尋最終的結果
2. 下為0，上為Integer.MAX_VALUE
3. 每次都檢查是否這個score可以是答案(這裡檢查的部分就是我無法完全懂的地方)
   1. 每次都檢查前數 + score是否大於當前數字 + d，如果大於就代表這個score是不可能的
   2. 通過就更新前數為前數 + score或當前數字取最大值
   3. 全部檢查完都通過就回傳true

這裡我不理解為什麼這樣檢查前數 + score是否大於當前數字 + d就可以確保score是valid…

Code

網友解答

class Solution {
    public int maxPossibleScore(int[] start, int d) {
        int l = 0, r = Integer.MAX_VALUE;
        int res = 0;
        Arrays.sort(start);

        // Search for the possible score
        while (l <= r) {
            // Possible score
            int mid = l + (r - l) / 2;

            if (isValid(start, d, mid)) {
                res = mid;
                l = mid + 1;
            } else {
                r =  mid - 1;
            }
        }
        return res;
    }

    private boolean isValid(int[] nums, int d, int possibleScore) {
        int prev = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            // Exceed the maximum day
            if (prev + possibleScore > nums[i] + d) return false;
            // Update previous value
            prev = Math.max(prev + possibleScore, nums[i]);
        }
        return true;
    }
}