侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【二分查找】分割数组的最大值

GabrielxD
2022-10-19 / 0 评论 / 0 点赞 / 11 阅读 / 508 字 / 正在检测是否收录...

题目

410. 分割数组的最大值


给定一个非负整数数组 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] <= 10^6
  • 1 <= m <= min(50, nums.length)

解题

方法一:二分查找

思路

这题看似很难,感觉要上动态规划,但其实仔细读题就会发现这题和【二分查找】在 D 天内送达包裹的能力是一模一样的,甚至把解题代码复制过来改一下函数名就可以过。

代码

class Solution {
    int f(vector<int>& nums, int sum) {
        int curr = 0, split = 0;
        for (int& num : nums) {
            if (curr + num >= sum) {
                curr = curr + num > sum ? num : 0;
                ++split;
            } else curr += num;
        }
        if (curr > 0) ++split;
        return split;
    }

public:
    int splitArray(vector<int>& nums, int k) {
        int left = 0, right = 0;
        for (int& num : nums) {
            left = max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (f(nums, mid) <= k) right = mid;
            else left = mid + 1; 
        }
        return left;
    }
};
class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0, right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(nums, k, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    boolean check(int[] nums, int k, int sum) {
        int curr = 0, split = 0;
        for (int num : nums) {
            if (curr + num >= sum) {
                curr = curr + num > sum ? num : 0;
                if (++split > k) return false;
            } else curr += num;
        }
        if (curr > 0) ++split;
        return split <= k;
    }
}
0

评论区