有界数组指定下标处的最大值

5711. 有界数组中指定下标处的最大值

难度中等

给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：

• nums.length == n
• nums[i] 是 正整数 ，其中 0 <= i < n
• abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
• nums 中所有元素之和不超过 maxSum
• nums[index] 的值被 最大化

返回你所构造的数组中的 nums[index] 。

注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。

示例 1：

输入：n = 4, index = 2,  maxSum = 6
输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。

示例 2：

输入：n = 6, index = 1,  maxSum = 10
输出：3

提示：

• 1 <= n <= maxSum <= 109
• 0 <= index < n

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int max = maxSum / n + n / 2;
        int res = 1;
        int left = 1, right = max;
        while (left <= right) {

            int mid = left + (right - left) / 2;
            
            // 左边的首项（后面会继续处理）
            int f = mid - index;
            // 右边的首项(后面会继续处理)
            int l = mid - (n - index - 1);
            
            long leftMin = 0;
            long rightMin = 0;

            if (f < 1) {
                // 左边除等差数列外剩余的1的数量
                int fTsum = 1 - f;
                // 首项是1的时候左边的最小和
                // 1是首项,mid-1是尾项，数字的数量是mid-1
                // 左边的等差数列的和是(1 + mid - 1) * (mid - 1) / 2,其中还有fTsum个1
                leftMin = (long) (1 + mid - 1) * (mid - 1) / 2 + fTsum;
            } else {
                // 首项不是1的时候左边的最小和
                // f是首项,mid-1是尾项,数字的数量是mid-f,
                // 左边的等差数列的和是(f + mid - 1) * (mid - f) / 2
                leftMin = (long) (f + mid - 1) * (mid - f) / 2;
            }

            if (l < 1) {
                // 右边除等差数列外剩余的1的数量
                int lTsum = 1 - l;
                // 首项是1的时候左边的最小和
                // 1是首项,mid-1是尾项，数字的数量是mid-1
                // 右边的等差数列的和是(1 + mid - 1) * (mid - 1) / 2,其中还有lTsum个1
                rightMin = (long) (1 + mid - 1) * (mid - 1) / 2 + lTsum;
            } else {
                // 首项不是1的时候左边的最小和
                // f是首项,mid-1是尾项,数字的数量是mid-l,
                // 右边的等差数列的和是(l + mid - 1) * (mid - l) / 2
                rightMin = (long) (l + mid - 1) * (mid - l) / 2;
            }
            // 如果满足条件，那么可以继续增加index的值试探
            if (leftMin + rightMin + mid <= maxSum) {
                res = Math.max(mid, res);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;

    }
}

赏

谢谢你请我吃糖果

微信