1. //给你一个整数数组 bloomDay，以及两个整数 m 和 k 。 
    2. //
    3. // 现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。 
    4. //
    5. // 花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。 
    6. //
    7. // 请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。 
    8. //
    9. // 
    10. //
    11. // 示例 1： 
    12. //
    13. // 输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
    14. //输出：3
    15. //解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
    16. //现在需要制作 3 束花，每束只需要 1 朵。
    17. //1 天后：[x, _, _, _, _]   // 只能制作 1 束花
    18. //2 天后：[x, _, _, _, x]   // 只能制作 2 束花
    19. //3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3
    20. // 
    21. //
    22. // 示例 2： 
    23. //
    24. // 输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
    25. //输出：-1
    26. //解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。
    27. // 
    28. //
    29. // 示例 3： 
    30. //
    31. // 输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
    32. //输出：12
    33. //解释：要制作 2 束花，每束需要 3 朵。
    34. //花园在 7 天后和 12 天后的情况如下：
    35. //7 天后：[x, x, x, x, _, x, x]
    36. //可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
    37. //12 天后：[x, x, x, x, x, x, x]
    38. //显然，我们可以用不同的方式制作两束花。
    39. // 
    40. //
    41. // 示例 4： 
    42. //
    43. // 输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
    44. //输出：1000000000
    45. //解释：需要等 1000000000 天才能采到花来制作花束
    46. // 
    47. //
    48. // 示例 5： 
    49. //
    50. // 输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
    51. //输出：9
    52. // 
    53. //
    54. // 
    55. //
    56. // 提示： 
    57. //
    58. // 
    59. // bloomDay.length == n 
    60. // 1 <= n <= 10^5 
    61. // 1 <= bloomDay[i] <= 10^9 
    62. // 1 <= m <= 10^6 
    63. // 1 <= k <= n 
    64. // 
    65. // Related Topics 数组 二分查找 
    66. // 👍 61 👎 0

    这是周赛一道第三题，当时的思路并不清晰，一直在子数组中游荡，赛后看别人题解的时候也想不通，为什么会用二分来做。
    这题实际上和子数组没关系，要求一个符合要求的最小值， 那么无论子数组怎么取，目的是获取这个最小值。
    而且范围已经给定出来了，1 <= bloomDay[i] <= 10^9 。
    所以直接二分的去查找，第i天能否制作出m束花，如果不行，就排除了一半的天数，小于i天的也做不出来。如果i天可以做出来，那么i天以后的也依然可以做出来，可以寻找比i小的数去寻找极值。
    问题就转化为了，限制天数，判断该天能否做出符合条件的花

    1. class Solution {
    2.     public int minDays(int[] bloomDay, int m, int k) {
    3.         if (bloomDay.length < m * k){
    4.             return -1;
    5.         }
    6.         int left = 0;
    7.         int right = 0;
    8.         // 二分的左右边界分别是0和数组的最大值，[0, max_value]
    9.         for (int i = 0; i < bloomDay.length; i++) {
    10.             right = Math.max(right, bloomDay[i]);
    11.         }
    13.         while (left < right){
    14.             // 开始二分的取天数
    15.             int mid = left + (right - left) / 2;
    17.             // mid天做花，可以做几束
    18.             int count = getCount(bloomDay, mid, k);
    19.             if (m <= count){
    20.                 // 如果第mid天可以做出符合要求的花，可以尝试向更小的值查找， 排除了mid之后的答案
    21.                 right = mid;
    22.             }else {
    23.                 // 如果mid天做不出符合要求的花，排除了mid之前的答案
    24.                 left = mid + 1;
    25.             }
    26.         }
    27.         return left;
    28.     }
    30.     // 计算有多少个连续k朵成熟天数都小于k的
    31.     public int getCount(int[] bloomDay, int limit, int k){
    32.         int res = 0;
    33.         int cur = 0;
    34.         for (int i = 0; i < bloomDay.length; i++) {
    35.             if (bloomDay[i] <= limit){
    36.                 cur ++;
    37.                 if (cur == k){
    38.                     res ++;
    39.                     cur = 0;
    40.                 }
    41.             }else {
    42.                 cur = 0;
    43.             }
    44.         }
    45.         return res;
    46.     }
    47. }