Сложность: easy
Учитывая целочисленный массив nums и целое число k, разбейте nums на k непустых подмассивов так, чтобы наибольшая сумма любого подмассива была минимальна. Верните минимизированную наибольшую сумму разбиения. Подмассив - это смежная часть массива.
Пример:
Input: nums = [7,2,5,10,8], k = 2
Output: 18
👨💻 Алгоритм:
1⃣Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива.
2⃣Выполните бинарный поиск по этим границам. Для каждой средней суммы проверьте, можно ли разбить массив на k подмассивов, чтобы максимальная сумма подмассива не превышала эту среднюю сумму.
3⃣Если возможно разбить массив для данной средней суммы, уменьшите верхнюю границу. Если нет, увеличьте нижнюю границу. Повторяйте до тех пор, пока границы не сойдутся.
😎 Решение:
func splitArray(_ nums: [Int], _ k: Int) -> Int {
var left = nums.max()!
var right = nums.reduce(0, +)
while left < right {
let mid = (left + right) / 2
if canSplit(nums, k, mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
func canSplit(_ nums: [Int], _ k: Int, _ maxSum: Int) -> Bool {
var currentSum = 0
var subarrays = 1
for num in nums {
if currentSum + num > maxSum {
currentSum = num
subarrays += 1
if subarrays > k {
return false
}
} else {
currentSum += num
}
}
return true
}Ставь 👍 и забирай 📚 Базу знаний