前言
持续更新了
正文
问题来源
本问题来自leetcode上的410题。
问题描述
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1:
输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
分析：
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func binSearch(nums []int, start, end, tag int) int {
l, r := start, end
for l <= r {
mid := (l+r) / 2
if tag == nums[mid] {
return mid
} else if tag < nums[mid] {
r = mid-1
} else {
l = mid+1
}
}
return r
}
func splitArray(nums []int, m int) int {
res := math.MaxInt32
for i := 1; i < len(nums); i++ {
nums[i] += nums[i-1]
}
nums = append([]int{0}, nums...)
if m == 1 {
return nums[len(nums)-1]
}
cmax := (nums[len(nums)-1]+m-1)/m
dfs(nums, 0, m, cmax, &res)
return res
}
func dfs(nums []int, start int, m int, cmax int, res *int) {
if m == 1 {
cmax = max(cmax, nums[len(nums)-1]-nums[start])
*res = min(*res, cmax)
return
}
if cmax > *res {
return
}
index := binSearch(nums, start+1, len(nums)-m, nums[start]+cmax)
dfs(nums, index, m-1, max(cmax,(nums[len(nums)-1]-nums[index]+m-1)/m-1), res)
if index < len(nums)-m {
dfs(nums, index+1, m-1, max(cmax, nums[index+1]-nums[start]), res)
}
}
本题中，我们注意到：当我们选定一个值 x，我们可以线性地验证是否存在一种分割方案，满足其最大分割子数组和不超过 x。策略如下：
贪心地模拟分割的过程，从前到后遍历数组，用 sum 表示当前分割子数组的和，cnt 表示已经分割出的子数组的数量（包括当前子数组），那么每当 sum 加上当前值超过了 x，我们就把当前取的值作为新的一段分割子数组的开头，并将 cnt 加 1。遍历结束后验证是否 cnt 不超过 m。
这样我们可以用二分查找来解决。二分的上界为数组 nums 中所有元素的和，下界为数组 nums 中所有元素的最大值。通过二分查找，我们可以得到最小的最大分割子数组和，这样就可以得到最终的答案了。
func max(a, b int) int {
if a > b {
return a
}
return b
}
func check(nums []int, tmax, m int) bool {
count := 1
total := 0
for _, v := range nums {
if total + v > tmax {
total = v
count++
} else {
total += v
}
}
return count <= m
}
func splitArray(nums []int, m int) int {
l, r := 0, 0
for _, v := range nums {
r += v
l = max(l, v)
}
for l < r {
mid := (r+l)/2
if check(nums, mid, m) {
r = mid
} else {
l = mid+1
}
}
return l
}
总结：
勤思考。
结语
不管怎么样好好加油。
