Re: [閒聊] 每日LeetCode
2439. Minimize Maximum of Array
給你一個陣列 nums ，你可以做無限次數的下列一串操作(必須同時做)：
1. i 必須滿足 1 <= i < n 且 nums[i] > 0
2.把 nums[i - 1] 遞增
3.把 nums[i] 遞減
試求經過多次操作後，陣列裡的最大值是多少? 這個最大值要盡可能小。
Example:
Input: nums = [3,7,1,6]
Output: 5
Explanation:
One set of optimal operations is as follows:
1. Choose i = 1, and nums becomes [4,6,1,6].
2. Choose i = 3, and nums becomes [4,6,2,5].
3. Choose i = 1, and nums becomes [5,5,2,5].
The maximum integer of nums is 5. It can be shown that the maximum number
cannot be less than 5.
Therefore, we return 5.
Input: nums = [10,1]
Output: 10
Explanation:
It is optimal to leave nums as is, and since 10 is the maximum value, we
return 10.
思路：
1.題目給的操作告訴我們可以把右邊數字的數量往左移，我們必須找出一個數字可以
滿足所有的數字透過多次左移後都小於等於他，要取下界那就是二分搜索了。
2.搜索範圍會是(0, MAX(nums))，攥寫一個函數檢查當前的數字是不是合法，用
have紀錄左邊還可以被右邊填充多少數量，如果檢查結果不合法就往右半邊繼續搜索
，否則把右邊界固定為當前邊界。
Java Code：
----------------------------------------
class Solution {
public int minimizeArrayValue(int[] nums) {
int left = 0;
int right = nums[0];
for (int num : nums) {
right = Math.max(right, num);
}
while (left < right) {
int mid = (left + right)/2;
if (check(nums, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean check(int[] nums, int n) {
// 用long才不會溢位
long have = 0;
for (int num : nums) {
if (num <= n) {
// 把左邊的剩餘空間保存
have += (n - num);
} else {
// 剩餘空間不夠就返回false
if (have < num - n) {
return false;
}
have -= (num - n);
}
}
return true;
}
}
----------------------------------------
二分搜索.... 真的好難
https://i.imgur.com/XJKs6rN.png
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680697803.A.297.html
推
04/05 20:37,
2年前
, 1F
04/05 20:37, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 284 之 719 篇)：