二分查找
解题思路
可以用于查找一个 有范围的 整数，就能想到是不是可以使用二分查找去解决这道问题；
这道题是对结果的二分，同 leetcode🧑💻 410. 分割数组的最大值 题解一致，只是换了种方式表达；
复杂度
-
时间复杂度：
O(nlog(high − low))，其中遍历数组花费时间为O(n)，在 [high, low] 区间内二分花费的时间为O(log(high − low)) -
空间复杂度：
O(1)
代码实现
var minDays = function (bloomDay, m, k) {
if (bloomDay.length < m * k) {
return -1;
}
let left = Math.min(...bloomDay);
let right = Math.max(...bloomDay);
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
if (check(bloomDay, k, mid) < m) {
left = mid + 1; // 花束小于 m，需要增加花束的数量，即区间为 [mid+1，right]
} else {
right = mid; // 花束大于等于 m，需要减少花束的数量，即区间为 [mid，right]
}
}
return left;
};
/**
* @param { Array<number> } bloomDay
* @param { number } k 相邻的 k 朵花
* @param { number } minDay 给定天数
* @returns { number } 给定天数内 minDay 能采摘几束花
*/
function check(bloomDay, k, minDay) {
let currLoop = 0; // 记录连续的花
let num = 0; // 采摘花是几束花
for (const item of bloomDay) {
if (item <= minDay) {
currLoop++; // 连续，记录 currLoop
if (currLoop == k) {
// 连续的花够几束
num++;
currLoop = 0;
}
} else {
currLoop = 0; // 不连续，清零
}
}
return num;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 1011. 在 D 天内送达包裹的能力
上一篇
评论
