大望路网站建设,个人免费网站建站关键词,网站域名不备案,网站建设的栏目规划文章目录 LeetCode#xff1f;启动#xff01;#xff01;#xff01;题目#xff1a;分割数组的最大值题目描述代码与解题思路 LeetCode#xff1f;启动#xff01;#xff01;#xff01; 今天是 hard#xff0c;难受#xff0c;还好有题解大哥的清晰讲解
题目启动题目分割数组的最大值题目描述代码与解题思路 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, (leftright)/2for _, v : range nums {tmp vif tmp mid { // 凑成子数组的最大和了, 计数, tmp 从当前值重新开始计算cnttmp v}}cnt // 加上最后的那个数组if cnt k { // 达成最大和 mid 的子数组数量多了, 证明 mid 不够大left mid 1} else { // 达成最大和的子数组少了, 证明最大和要求太大, 需要变小一些right mid}}return left
}由题意可知子数组的最大范围是 [max(nums), sum(nums)]
令 left max_numsright sum_numsmid (left right) / 2
计算数组和 mid 对应的子数组数量 cnt直到找到与子数组 k 数量相匹配的最大数组和即可
当 cnt k就证明子数组划分多了mid 偏小令 left mid 1 当 cnt k就证明子数组少了或者刚刚好令 right mid
