LeetCode 1482：制作m束花的最少天数代码返回结果错误排查

问题场景 #

我在解决LeetCode 1482. Minimum Number of Days to Make m Bouquets问题时，采用二分查找思路确定最少天数，但遇到测试用例错误：

• 测试用例：bloomDay = [1,10,3,10,2]，m = 3，k = 1
• 代码返回结果：10
• 预期输出：3

原代码如下：

def minDays(self, bloomDay, m, k):
    """
    :type bloomDay: List[int]
    :type m: int
    :type k: int
    :rtype: int
    """
    def possible(arr, day, m, k):
        count = 0
        possible_b = 0
        for i in range(len(arr)):
            if arr[i] <= day:
                count += 1
            else:
                possible_b += count // k
                count = 0
        # 这里是错误所在
        possible_b = count // k
        return possible_b >= m

    low = 1
    high = max(bloomDay)
    n = len(bloomDay)
    if k * m > n:
        return -1
    while low <= high:
        mid = (low + high) // 2
        if possible(bloomDay, mid, m, k):
            high = mid - 1
        else:
            low = mid + 1
    return low

错误原因分析 #

问题出在possible函数的最后一步：
遍历结束后，你直接用possible_b = count // k覆盖了之前累加的结果，而不是累加最后一段连续盛开的花束数到possible_b中。

以测试用例day=3为例：

1. 遍历到第1朵花（10>3）时，possible_b累加为1（1//1），count重置为0
2. 遍历到第3朵花（10>3）时，possible_b累加为2（1//1），count重置为0
3. 遍历结束后，最后一段count=1（第4朵花2<=3），此时你执行possible_b = count//k，把possible_b从2改成了1，导致最终possible_b=1 < 3，返回False
4. 二分查找因此错误判定day=3不满足条件，持续增大low直到day=10才返回True

修正方案 #

将possible函数最后一行的赋值操作改为累加操作：

possible_b += count // k

修正后的完整代码：

def minDays(self, bloomDay, m, k):
    """
    :type bloomDay: List[int]
    :type m: int
    :type k: int
    :rtype: int
    """
    def possible(arr, day, m, k):
        count = 0
        possible_b = 0
        for i in range(len(arr)):
            if arr[i] <= day:
                count += 1
            else:
                possible_b += count // k
                count = 0
        # 修正为累加最后一段的花束数
        possible_b += count // k
        return possible_b >= m

    low = 1
    high = max(bloomDay)
    n = len(bloomDay)
    if k * m > n:
        return -1
    while low <= high:
        mid = (low + high) // 2
        if possible(bloomDay, mid, m, k):
            high = mid - 1
        else:
            low = mid + 1
    return low

修正效果 #

当day=3时，遍历结束后possible_b会累加最后一段的1//1=1，最终possible_b=2+1=3，满足>=m=3的条件，返回True。二分查找会正确缩小high的范围，最终得到正确结果3。

内容的提问来源于stack exchange，提问作者Piyush Sharma_ 45