二分搜索应用 II

LARRY1024 / 2024-01-22 / 原文

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

1. 题目列表

题目列表：

序号	题目	难度
1	410. 分割数组的最大值	困难

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$，在所有情况中最小。

提示：

$1 <= nums.length <= 1000$
$0 <= nums[i] <= 10^6$
$1 <= k <= min(50, nums.length)$

2.1.2. 解题思路

题目中要求将数组 $nums$ 分成 $k$ 个非空连续子数组，使得每个子数组的和尽可能小，同时，分割的子数组个数又恰好等于 $k$，那么，对于分割的方式必然存在单调性，因此，我们可以使用二分搜索的方式求解。

设数组 $nums$ 的长度为 $n$，显然，每个区间和的最小值就是数组中的最大值，同时，不超过数组所有元素的和，那么

二分查找的右侧区间就是 $left = \max_{i=0}^{n}nums[i]$；
二分查找的右侧区间就是 $right = \sum_{i=0}^{n}nums[i]$。

那么，只需要在闭区间 $[left, right] = [\max_{i=0}^{n}nums[i], \ \sum_{i=0}^{n}nums[i]]$ 内，多次进行二分查找，只要某一个数组和恰好可以使数组分割为 $k$，即可退出查找。

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 = maxNum;
        int right = sum;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 分割次数大于k，说明每一段的目标和太小了，需要缩小左区间
            if (check(nums, k, mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }

    private boolean check(int[] nums, int k, int target) {
        int splitCount = 1; // 以当前的区间中点作为子数组的和，可以分割的次数
        int sum = 0;
        for (int num : nums) {
            if (sum + num <= target) {
                sum += num;
            } else {
                // 若分割次数大于k，则需要缩小区间左边界
                splitCount++;
                if (splitCount > k) {
                    return true;
                }
                sum = num;
            }
        }
        return false;
    }
}