Leetcode 1482. 制作 m 束花束的最少天数：返回太多天

Question

我正在尝试解决LeetCode问题1482。制作 m 束花束的最少天数:

您将获得一个整数数组

bloomDay

、一个整数

m

和一个整数

k

。

您想要制作

m

花束。要制作花束，您需要使用花园中的

k

相邻的花朵。

花园由

n

花组成，

ith

花会在

bloomDay[i]

中盛开，然后可以用于制作一束花。

返回您需要等待才能制作

m

花园花束的最短天数。如果无法使

m

花束返回-1.

我想用二分查找来确定最小天数，通过尝试二分查找中访问过的每个数字，看看是否有可能在该天数内实现目标。

这是我的代码：

   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
            if possible_b>=m:
                return True
            else:
                return False
        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)==True:
                high=mid-1
            else:
                low=mid+1
        return low  

问题

对于以下测试用例，我的代码返回错误的答案：

bloomDay = [1,10,3,10,2], m = 3, k = 1

预期输出是 3，但我的代码返回 10。

我在这里缺少什么？

Answer 1

问题出在函数

possible

中，在这一行：

            possible_b=count//k

这会覆盖您在循环中已经累积的计数。

相反，您应该将它们添加到您已有的内容中：

possible_b += count//k 此修复解决了问题。