LeetCode 0410.分割数组的最大值:二分

发布时间:2024年01月21日

【LetMeFly】410.分割数组的最大值:二分

力扣题目链接:https://leetcode.cn/problems/split-array-largest-sum/

给定一个非负整数数组 nums 和一个整数?m ,你需要将这个数组分成?m?个非空的连续子数组。

设计一个算法使得这?m?个子数组各自和的最大值最小。

?

示例 1:

输入:nums = [7,2,5,10,8], m = 2
输出:18
解释:
一共有四种方法将 nums 分割为 2 个子数组。 
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。

示例 2:

输入:nums = [1,2,3,4,5], m = 2
输出:9

示例 3:

输入:nums = [1,4,4], m = 3
输出:4

?

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 106
  • 1 <= m <= min(50, nums.length)

方法一:二分

写一个函数check(s),返回能否将数组nums划分为k部分且每一部分的最大值不超过s

实现方法很简单,使用一个变量cnt来记录当前部分的元素和。

遍历数组,如果当前元素大于s,则必不可能成功划分,直接返回false

cnt加上当前元素超过了s,则将当前元素划分为一组(k--cnt = 0)。

cnt加上当前元素。

遍历结束后,判断k - 1是否大于等于0。若是,则返回true,否则返回false

有了这样的函数,我们只需要在主函数中写一个二分,枚举值mid是否能通过check

l初始值为0r初始值为“无穷大”(数组中所有元素之和再加一)。

l < r时,令 m i d = ? l + r 2 ? mid = \lfloor \frac{l+r}{2} \rfloor mid=?2l+r??

如果check(mid)通过了,则说明mid为一种合法分法,尝试更小的值能否成功划分(令r = mid

否则,说明mid太小了,无法划分,尝试更大的值能否成功划分(令l = mid + 1

二分结束后,l = r,返回l即为答案。

  • 时间复杂度 O ( l e n ( n u m s ) × log ? ∑ n u m s ) O(len(nums)\times \log \sum nums) O(len(nums)×lognums)
  • 空间复杂度 O ( 1 ) O(1) O(1)

AC代码

C++
class Solution {
private:
    bool check(vector<int>& nums, int k, int s) {
        int cnt = 0;
        for (int t : nums) {
            if (t > s) {
                return false;
            }
            if (t + cnt > s) {
                k--;
                cnt = 0;
            }
            cnt += t;
        }
        return --k >= 0;
    }
public:
    int splitArray(vector<int>& nums, int k) {
        int l = 0, r = accumulate(nums.begin(), nums.end(), 0) + 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(nums, k, mid)) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        return l;
    }
};
Python
# from typing import List

class Solution:
    def check(self, k: int, s: int) -> bool:
        cnt = 0
        for t in self.nums:
            if t > s:
                return False
            if cnt + t > s:
                k -= 1
                cnt = 0
            cnt += t
        return k - 1 >= 0

    def splitArray(self, nums: List[int], k: int) -> int:
        self.nums = nums
        l, r = 0, sum(nums) + 1
        while l < r:
            mid = (l + r) >> 1
            if self.check(k, mid):
                r = mid
            else:
                l = mid + 1
        return l

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/135728821

文章来源:https://blog.csdn.net/Tisfy/article/details/135728821
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。