题目

image.png

思路

  • 典型的二分，我们可以知道如果mid天能够得到m组k束花，那么比mid大的所有天数都是可以的，我们现在就要看能否在更少的天数获得m*k朵花。

    代码

    2.   //2.二分法
    3.   public int minDays(int[] bloomDay, int m, int k) {
    4.       int len = bloomDay.length, size = m * k;
    5.       if (len < size) return -1;
    6.       int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    7.       for (int day : bloomDay) {
    8.           min = Math.min(min, day);
    9.           max = Math.max(max, day);
    10.       }
    11.       while (min < max) {
    12.           int mid = (min + max) / 2;
    13.           int count = getCount(bloomDay, k, mid);
    14.           if (count >= m) {
    15.               max = mid;
    16.           } else {
    17.               min = mid + 1;
    18.           }
    19.       }
    20.       return min;
    21.   }
    22.   //统计在不同天数下，连续能满足的情况
    23.   public int getCount(int[] bloomDay, int k, int mid) {
    24.       int count = 0, res = 0;
    25.       for (int day : bloomDay) {
    26.           count = day <= mid ? count + 1 : 0; 
    27.           if (count == k) {
    28.               count = 0;
    29.               res++;
    30.           }
    31.       }
    32.       return res;

    制作m束花所需的最少天数
    [同系列]爱吃香蕉的珂珂
    [同系列]分割数组的最大值