【LeetCode】每日一题 2024_1_21 分割数组的最大值（二分）

LeetCode？启动！！！

今天是 hard，难受，还好有题解大哥的清晰讲解

题目：分割数组的最大值

题目链接：410. 分割数组的最大值

题目描述

代码与解题思路

func splitArray(nums []int, k int) int {// max_nums 是 nums 中最大的一个数, sum_nums 是 nums 所有数的和max_nums, sum_nums := 0, 0for _, v := range nums {sum_nums += vmax_nums = max(max_nums, v)}// 用二分思想猜出使用 k 个子数组的最大和left, right := max_nums, sum_numsfor left < right {tmp, cnt, mid := 0, 0, (left+right)/2for _, v := range nums {tmp += vif tmp > mid { // 凑成子数组的最大和了, 计数++, tmp 从当前值重新开始计算cnt++tmp = v}}cnt++ // 加上最后的那个数组if cnt > k { // 达成最大和 mid 的子数组数量多了, 证明 mid 不够大left = mid + 1} else { // 达成最大和的子数组少了, 证明最大和要求太大, 需要变小一些right = mid}}return left
}

由题意可知，子数组的最大范围是 [max(nums), sum(nums)]

令 left = max_nums，right = sum_nums，mid = (left + right) / 2

计算数组和 mid 对应的子数组数量 cnt，直到找到与子数组 k 数量相匹配的最大数组和即可

当 cnt > k，就证明子数组划分多了，mid 偏小，令 left = mid + 1
当 cnt <= k，就证明子数组少了（或者刚刚好），令 right = mid