贪心-LeetCode410. 分割数组的最大值

1、题目描述

https://leetcode-cn.com/problems/split-array-largest-sum/

给定一个非负整数数组和一个整数 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，在所有情况中最小。

 

2、代码详解

为什么要贪心地使子数组和不断逼近mid？

• 我先猜一个mid值，然后遍历数组划分，使每个子数组和都最接近mid（贪心地逼近mid），这样我得到的子数组数一定最少;
• 如果即使这样子数组数量仍旧多于m个，那么明显说明我mid猜小了，因此 lo = mid + 1;
• 而如果得到的子数组数量小于等于m个，那么我可能会想，mid是不是有可能更小？值得一试。因此 hi = mid;

 

class Solution(object):
    def splitArray(self, nums, m):
        # 由于题目的返回要求：返回最小和的值
        # 最小和必然在 [max(nums), sum(nums)] 间
        # 可以使用二分来进行查找
        low, high = max(nums), sum(nums)
        while low < high:
            mid = (low + high) // 2
            # 淘汰算法
            # 数组分成 m 个非空的连续子数组
            # 由前向后对nums进行划分，使其子数组和 <= mid，然后统计满足条件的数组数量
            # 若我们选的sum值过小，则满足条件的数量 > m，目标值应落在 [mid+1, high]
            # 若我们选的sum值过大，则满足条件的数量 < m，目标值应落在 [low, mid-1]
            count = 0
            sub_sum = 0
            for i in range(len(nums)):
                sub_sum += nums[i]
                if sub_sum > mid:
                    count += 1
                    sub_sum = nums[i]
            # 注意：末尾还有一个子数组我们没有统计，这里把它加上
            count += 1
            if count > m:
                low = mid + 1
            else:
                high = mid
        return low

nums = [7, 2, 5, 10, 8]
# # 分为[7,2,5]  [10,8]， 此时这两个子数组各自的和的最大值为18，在所有情况中最小。
m = 2
s = Solution()
print(s.splitArray(nums, m))

 

本文地址：https://blog.csdn.net/IOT_victor/article/details/107581397