最大化最小值
分享巧克力【LC1231】
You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.
You want to share the chocolate with your k friends so you start cutting the chocolate bar into k + 1 pieces using k cuts, each piece consists of some consecutive chunks.
Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.
Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.
你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。
你打算和 K 名朋友一起分享这块巧克力，所以你需要将切割 K 次才能得到 K+1 块，每一块都由一些 连续 的小块组成。
为了表现出你的慷慨，你将会吃掉 总甜度最小 的一块，并将其余几块分给你的朋友们。
请找出一个最佳的切割策略，使得你所分得的巧克力 总甜度最大，并返回这个 最大总甜度。
思路：
- 题意：将数组
sweetness分割成连续的k+1个子数组，返回分割后的子数组中和最小的最大值。 - 本题的单调性为：当**最小甜度【连续子数组和的最小值】**最大，最多分割的份数越小，那么可以通过二分查找法找到最终答案
class Solution { public int maximizeSweetness(int[] sweetness, int k) { int n = sweetness.length; int[] preSum = new int [n + 1]; for (int i = 0; i < n; i++){ preSum[i + 1] = preSum[i] + sweetness[i]; } int l = 1, r = preSum[n] / (k + 1); int ans = 0; while (l <= r){ int mid = (l + r) / 2; if (check(mid, preSum, k + 1)){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } return ans; } public boolean check(int min, int[] preSum, int k){ int count = 0; int preIndex = 0; for (int i = 1; i < preSum.length; i++){ if (preSum[i] - preSum[preIndex] >= min){ count++; preIndex = i; } } return count >= k; } }
class Solution { public int maximizeSweetness(int[] sweetness, int k) { int n = sweetness.length; int sum = 0; for (int i = 0; i < n; i++){ sum += sweetness[i]; } int l = 1, r = sum / (k + 1); int ans = 0; while (l <= r){ int mid = (l + r) / 2; if (check(mid, sweetness, k + 1)){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } return ans; } public boolean check(int min, int[] sweetness, int k){ int count = 0; int sum = 0; for (int i = 0; i < sweetness.length; i++){ sum += sweetness[i]; if (sum >= min){ count++; sum = 0; } } return count >= k; } }
两球间的磁力【LC1552】
在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有
n个空的篮子，第i个篮子的位置在position[i]
Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。
已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。
给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
思路：
- 首先，二分查找的核心就是找到具有单调性的正确查找对象（来自北枝大佬）
- 一般来说，查找对象就是题目要求的值，这里为最小磁力【最小球间距】
- 本题的单调性为，最小磁力越大，最多能放置的球的个数越小
class Solution { public int maxDistance(int[] position, int m) { Arrays.sort(position); int n = position.length; int l = 1, r = position[n - 1] - position[0]; int ans = 0; while (l <= r){ int mid = (l + r) / 2; if (check(mid, position, m)){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } return ans; } public boolean check (int y, int[] position, int m){ int count = 1; int pre = position[0]; for (int i = 1; i < position.length; i++){ if (position[i] - pre >= y){ count++; pre = position[i]; } } return count >= m; } }
礼盒的最大甜蜜度【LC2517】
You are given an array of positive integers price where price[i] denotes the price of the ith candy and a positive integer k.
The store sells baskets of k distinct candies. The tastiness of a candy basket is the smallest absolute difference of the prices of any two candies in the basket.
Return the maximum tastiness of a candy basket.
思路：使用二分查找的方式寻找最大甜蜜度
- 本题的单调性为：当**最小甜蜜度【数组中任意两个元素的差值的绝对值的最小值】**越大，糖果的可以选择的种类越小【选取的数组中的元素个数】，因此可以通过二分查找法找到最终答案
class Solution { public int maximumTastiness(int[] price, int k) { Arrays.sort(price); int n = price.length; int l = 0, r = price[n - 1] - price[0]; int ans = 0; while (l <= r){ int mid = (r + l) / 2; if (check(price, mid ,k)){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } return ans; } public boolean check(int[] price, int m, int k){ int count = 1; int preIndex = 0; for (int i = 1; i < price.length; i++){ if (price[i] - price[preIndex] >= m ){ count++; preIndex = i; } } return count >= k; } }
