我和快手面试官对二分搜索进行了深度探讨 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：我和快手面试官对二分搜索进行了深度探讨

[2892514241]

这题似乎可以理解成leetcode 1011 的换皮，逻辑是一模一样的。 D天对应本题分割数组的数量m；按顺序装运对于本题的连续数组； 求最小运载能力即本题的求各数组和的最大值的最小值

[Stone-Fly]

我有个疑惑，这个算法最后的解，一定会是分割后的某个子数组的和吗，我感觉可能会不是，但是我想不出反例。

[2892514241]

题目要求返回的就是切割成m个子数组后和最大值中最小的那个，所以一定是某个子数组的和啊

[Stone-Fly]

我的意思是，算法要求的是子数组的和，但是算法计算的时候好像并没有哪句话能表明最后得到的解一定是子数组的和，因为计算过程是和小于等于max，所以按照我的理解，最后也有可能是会得到小于max的情况，那max不就不一定是子数组的和了吗。

[2892514241]

文章里提到了 可能存在多个 max 使得 split(nums, max) 算出相同的 n，因为我们的算法会返回最小的那个 max，所以应该使用搜索左侧边界的二分查找算法。 现在，问题变为：在闭区间 [lo, hi] 中搜索一个最小的 max，使得 split(nums, max) 恰好等于 m。

如果和的最大值(sum)比你当前的max小，那么这个sum就是更小的那个max，还是会被找到的

[rebel2019]

split函数貌似求不了最小值

[2892514241]

最小的max是用搜索左边界二分找的呀，不是用split函数求的 我的意思是你用左侧二分找到使得 split(nums, max) = m的最小值时，这个值一定是某个子数组的和 这个子数组的和是所有切分出来的子数组中和最大的值

[Marchxx]

往左侧搜索时，只会减小max，如果不是某个子数组的和，那就不是最小的那个值，还会二分下去

[Alwin4Zhang]

410. 分割数组的最大值（困难） python version

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def split(nums, _max):
            # 按照最大值是_max分组,不能大于_max
            count = gs = 0
            for i, num in enumerate(nums):
                if count + num <= _max:
                    count += num
                else:
                    count = num
                    gs += 1
            return gs + 1

        left, right = max(nums), sum(nums) + 1
        while left < right:  #  m 个子数组各自和的最大值最小，等同于左边界问题
            mid = left + (right - left) // 2
            gs = split(nums, mid)
            if gs > m:
                left = mid + 1
            else:  # gs <= m
                right = mid
        return left