电商网站如何优化,网站 用户体验,手机版的网站开发,模块网站需要多少钱文章目录 1. 题目链接2. 题目描述3. 题目示例4. 解题思路5. 题解代码6. 复杂度分析 1. 题目链接 2439. 最小化数组中的最大值 - 力扣#xff08;LeetCode#xff09;
2. 题目描述 给你一个下标从 0 开始的数组 nums #xff0c;它含有 n 个非负整数。
每一步操作中#… 文章目录 1. 题目链接2. 题目描述3. 题目示例4. 解题思路5. 题解代码6. 复杂度分析 1. 题目链接 2439. 最小化数组中的最大值 - 力扣LeetCode
2. 题目描述 给你一个下标从 0 开始的数组 nums 它含有 n 个非负整数。
每一步操作中你需要
选择一个满足 1 i n 的整数 i 且 nums[i] 0 。将 nums[i] 减 1 。将 nums[i - 1] 加 1 。
你可以对数组执行 任意 次上述操作请你返回可以得到的 nums 数组中 最大值 最小 为多少。 3. 题目示例 示例 1 : 输入nums [3,7,1,6]
输出5
解释
一串最优操作是
1. 选择 i 1 nums 变为 [4,6,1,6] 。
2. 选择 i 3 nums 变为 [4,6,2,5] 。
3. 选择 i 1 nums 变为 [5,5,2,5] 。
nums 中最大值为 5 。无法得到比 5 更小的最大值。
所以我们返回 5 。示例 2 : 输入nums [10,1]
输出10
解释
最优解是不改动 nums 10 是最大值所以返回 10 。4. 解题思路 二分查找确定候选值 最小可能值是0最大可能值是数组的初始最大值。通过二分法逐步缩小范围找到满足条件的最小最大值。 验证函数 (**check**) 从后向前遍历数组计算每个元素在给定候选值 limit 下是否需要转移多余的值到前一个元素。若所有元素最终能被调整到不超过 limit则候选值可行。 5. 题解代码 class Solution {public int minimizeArrayValue(int[] nums) {int left -1, right 0;// 初始化右边界为数组最大值for (int x : nums) right Math.max(right, x);// 二分查找找到最小的可行最大值while (left 1 right) {int mid (left right) / 2;if (check(nums, mid)) {right mid; // 可行尝试更小的值} else {left mid; // 不可行增大下界}}return right; // 最终 right 是最小可行最大值}// 验证函数判断是否所有元素可调整到不超过 limitprivate boolean check(int[] nums, int limit) {long extra 0; // 记录需要向前转移的“多余量”for (int i nums.length - 1; i 0; i--) {// 当前元素值加上之前的转移量若超过 limit则计算新的转移量extra Math.max(nums[i] extra - limit, 0);}// 最终检查第一个元素是否能容纳所有转移量return nums[0] extra limit;}
}6. 复杂度分析 时间复杂度O(n)其中n为nums的长度。空间复杂度O(1)仅用到若干变量。
