欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-31 10:57:56
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个子数组。.....

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