iT邦幫忙

1

【小馬的LeetCode練功坊】(難想到解法!)410. Split Array Largest Sum

今天分享leetcode的一道問題,
參考題目: 410. Split Array Largest Sum
(類似題: 1011. Capacity To Ship Packages Within D Days)

題意: 給你一個陣列nums,要求切成m個連續子陣列,
要求讓m個子陣列的總和的最大值愈小愈好

譬如:

Input: nums = [1,2,3,4,5,6,7,8,9,10], m = 5
Output: 15
說明: 最好的切割方法是
[1,2,3,4,5], [6,7], [8], [9], [10],
子陣列總和最大值是 1+2+3+4+5=15

解析:
其實一開始我看到這題也沒想法,
後來去查了題解發現可以用「二分搜索法」,
這題最難想的地方大概是:「原來二分搜索法可以用在這種地方啊」

考慮極端的狀況,若m = 1,子陣列就是原來的陣列,
答案就是sum(nums)

m = len(nums),每個子陣列僅一個元素,
答案就是max(nums)

當m介於兩者之間時,答案也一定在兩者的中間

對答案做二分搜索,首先寫一個函數叫做can_split(nums, m, ubd)
判斷說「是否有辦法將nums切成m塊子陣列,每塊的最大值不超過ubd」,
如果做的到,表示子陣列的總和的最大值有可能再小一點;
做不到的話,表示答案應該要再大一點

class Solution:
    #函數意義: 是否有辦法將nums切成m塊子陣列,每塊的最大值不超過ubd
    def can_split(self, nums, m, ubd):
        part, curSum = 1, 0
        for num in nums:
            curSum += num
            if curSum > ubd:
                curSum = num
                part+=1
                if part > m:
                    return False;
        return True

    def splitArray(self, nums: List[int], m: int) -> int:
        left, right = max(nums), sum(nums)
        while left < right:
            mid = left + (right - left) // 2
            if self.can_split(nums, m, mid):
                right = mid
            else:
                left = mid + 1
        return left

尚未有邦友留言

立即登入留言