二分查找之分割数组的最大值

LeetCode 410. 分割数组的最大值

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
示例:

输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

思路：
首先分析题意，可以得出结论，结果必定落在**【max（nums）， sum（nums）】**这个区间内，因为左端点对应每个单独的元素构成一个子数组，右端点对应所有元素构成一个子数组。

然后可以利用二分查找法逐步缩小区间范围，当区间长度为1时，即找到了最终答案。

每次二分查找就是先算一个mid值，这个mid就是代表当前猜测的答案，然后模拟一下划分子数组的过程，可以得到用这个mid值会一共得到的子区间数cnt，然后比较cnt和m的关系，来更新区间范围。

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        # max(nums), sum(nums)
        if len(nums) == m:
            return max(nums)
        left = max(nums)
        right = sum(nums)
        while left < right:
            mid = (left + right) // 2 # 最大和

            # 开始模拟切分数组
            temp = 0 # 初始第一个子数组和
            cnt = 1 # 数组个数初始化为1，说明还没有进行切分
            for num in nums:
                temp += num # 累加元素求和
                if temp > mid: #说明当前这个子数组的和已经超过了允许的最大值mid，需要把当前元素放在下一个子数组里
                    temp = num # 此时的num不能加入到当前子数组，要放到下一个子数组里
                    cnt += 1 # 切分了一个数组，cnt+1
            # 切分数组结束

            if cnt > m: # 说明分出了比要求多的子数组，多切了几刀，说明mid应该加大，这样能使子数组的个数减少
                left = mid + 1
            elif cnt <= m:
                right = mid
            
        return left

其他类似题目

LeetCode 875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：

输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2：

输入: piles = [30,11,23,4,20], H = 5
输出: 30

示例 3：

输入: piles = [30,11,23,4,20], H = 6
输出: 23

思路：
最小速度是1，最大速度是max(piles)，取中间速度，判断是否能在H小时内完成，如果可以，缩紧右边界，如果不可以，缩紧左边界，加快速度。

class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        left = 1
        right = max(piles) + 1
        while left < right:
            mid = left + (right - left) // 2
            # 以speed是否能在 H ⼩时内吃完⾹蕉
            if self.canFinish(piles, mid, H):
                right = mid
            else:
                left = mid + 1
        return left
    
    def canFinish(self, piles, speed, H):
        # 以speed是否能在 H ⼩时内吃完⾹蕉
        time = 0
        for n in piles:
            # 没吃完剩下的还得一小时
            remain = 0
            if n % speed != 0:
                remain = 1
            time += n // speed + remain

            if time > H:
                return False
        return time <= H
        

LeetCode 1014. 最佳观光组合

给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。

一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。

返回一对观光景点能取得的最高分。

示例：

输入：[8,1,5,2,6]
输出：11
解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

思路：
咋一看，很简单，代码撸完，超时
可以重新组合得分公式：（A[i] + i ）+ （A[j] - j）
这样就可以看成是左A[i]+i和右A[j]-j两部分和的最大值。这里A[i] + i 和 A[j] - j 相互独立
考虑约束条件i < j，于是形成动态规划的思路：

• 遍历A数组，求每个j下的A[j] - j的值，
• 再求i < j 下的max(A[i] + i)
• 最后再求所有遍历过程中的最大值就好了。

好了，看代码

def maxScoreSightseeingPair(self, A: List[int]) -> int:
        # 暴力超时解法
        # n = len(A)
        # score = -float('inf')
        # for i in range(n - 1):
        #     for j in range(i + 1, n):
        #         score = max(score, A[i] + A[j] + i - j)
        # return score
        
        # A[i]+i+A[j]-j
        left = A[0] + 0
        res = -1
        for j in range(1, len(A)):
            res = max(res, left + A[j] - j)
            left = max(left, A[j] + j)
        return res

本文地址：https://blog.csdn.net/andyjkt/article/details/107576251