1482.制作m束花所需的最少天数

链接：1482.制作m束花所需的最少天数
难度：Medium
标签：数组、二分查找
简介：请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

题解 1 - typescript

• 编辑时间：2021-05-09
• 执行用时：136ms
• 内存消耗：50.3MB
• 编程语言：typescript
• 解法介绍：二分法，通过最大日和最小日进行快速筛选。

function minDays(bloomDay: number[], m: number, k: number): number {
  const n = bloomDay.length;
  const minCount = m * k;
  if (n < minCount) return -1;
  if (k === 1) return bloomDay.sort((a, b) => a - b)[m - 1];
  const check = (day: number): boolean => {
    let count = 0;
    let flower = 0;
    for (let i = 0; i < n && count < m; i++) {
      if (bloomDay[i] <= day) {
        if (++flower === k) {
          flower = 0;
          count++;
        }
      } else {
        flower = 0;
      }
    }
    return count >= m;
  };
  let low = 0;
  let high = Math.max(...bloomDay);
  while (low < high) {
    const midDay = (low + high) >> 1;
    if (check(midDay)) high = midDay;
    else low = midDay + 1;
  }
  return low;
}