• 1. 题目列表
• 2. 应用
  • 2.1. Leetcode 410. 分割数组的最大值
    • 2.1.1. 题目
    • 2.1.2. 解题思路
    • 2.1.3. 代码实现

1. 题目列表

2. 应用

2.1. Leetcode 410. 分割数组的最大值

2.1.1. 题目

410. 分割数组的最大值

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
设计一个算法使得这 k 个子数组各自和的最大值最小。

示例 1：

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

2.1.2. 解题思路

2.1.3. 代码实现

class Solution {
    public int splitArray(int[] nums, int k) {
        int sum = 0;
        int maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        // 二分查找的区间
        int left = Math.max(maxNum - 1, (sum - 1) / k); // 最小值：分成多段，每段最少不小于最大值和平均值
        int right = sum; // 最大值：分成一段，就是sum
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(nums, k, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(int[] nums, int k, int target) {
        int count = 1;
        int sum = 0;
        // 计算这样分，最多可以分多少段
        for (int num : nums) {
            if (sum + num <= target) {
                sum += num;
            } else {
                if (count == k) {
                    return false;
                }
                // 新划分一段
                count += 1;
                // 并重新计算这一段的和
                sum = num;
            }
        }
        return true;
    }
}