Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-04-05 20:30:00
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:
作者: h0103661 (路人喵)   2023-04-05 20:37:00
这题设计还蛮有趣的,实际上是在求最大平均

Links booklink

Contact Us: admin [ a t ] ucptt.com