二分查找
解题思路
题意可以转换为：给定一个数组，将其划分成 M 份，使得每份元素之和最大值最小，每份可以任意减去其中一个元素（显然根据贪心的思路，是减去最大值）；也就是说二分的判定是：是否可以让每组删除最大值之后，总和都小于等于 t；
这道题是对结果的二分，同 leetcode🧑💻 410. 分割数组的最大值 题解一致，只是换了种方式表达；
复杂度
-
时间复杂度：
O(nlog(high − low))，其中遍历数组花费时间为O(n)，在 [high, low] 区间内二分花费的时间为O(log(high − low)) -
空间复杂度：
O(1)
代码实现
var minTime = function (time, m) {
if (time.length <= m) {
return 0;
}
let left = 0;
let right = time.reduce((sum, curr) => sum += curr, 0);
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
let dayNum = check(time, mid);
if (dayNum <= m) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
/**
* @param {*} arr
* @param {*} limit 解题时间
* @returns {} 每天只能花费 limit 时间去解题，需要多少天做完题
*/
const check = (arr, limit) => {
let sum = 0; // 当前区间的和
let max = 0; // 当前区间的最大值
let curr = 0; // 当前的元素
let num = 1;
for (let item of arr) {
curr = Math.min(max, item);
if (sum + curr <= limit) { // 每组删除最大值之后的总和
sum += curr;
max = Math.max(item, max);
} else { // 下一组
num++;
max = item;
sum = 0;
}
}
return num;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 1482. 制作 m 束花所需的最少天数
上一篇
评论
