1482. Minimum Number of Days to Make m Bouquets

题目 1482. Minimum Number of Days to Make m Bouquets

思路分析

代码实现

class Solution {

    private boolean check(int mid,int[] bloomDay,int m,int k){
        int n=bloomDay.length;
        int[] curDay = new int[n];
        for(int i=0;i<n;i++){
            curDay[i]=bloomDay[i]<=mid?1:0;
        }
        int cnt=0;
        for(int i=0;i<n;i++){
            int j=i;
            while(j<n && curDay[j]==1){
                j++;
            }
            cnt+=(j-i)/k;
            i=j;
        }
        return cnt>=m;
    }

    public int minDays(int[] bloomDay, int m, int k) {
        if ((long) m * k > bloomDay.length) {
            return -1;
        }
        int latest = 0;
        for(int day:bloomDay){
            latest=Math.max(day,latest);
        }
        int l=1,r=latest;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid,bloomDay,m,k)){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        return r;
    }
}

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        // 1. 预判：如果需要的花朵总数 > 现有的花朵总数，直接不可能
        // 注意：m * k 可能会超过 int 范围，必须转成 long
        if ((long) m * k > bloomDay.length) {
            return -1;
        }

        int maxDay = 0;
        int minDay = Integer.MAX_VALUE;
        for (int day : bloomDay) {
            maxDay = Math.max(maxDay, day);
            minDay = Math.min(minDay, day);
        }

        // 2. 二分查找范围
        // l 可以从 minDay 开始优化，r 是 maxDay
        int l = minDay, r = maxDay;

        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(mid, bloomDay, m, k)) {
                // 如果 mid 天能做完，说明时间够了，尝试缩短时间
                r = mid;
            } else {
                // 如果 mid 天做不完，说明时间太短，需要更多天
                l = mid + 1;
            }
        }
        return r;
    }

    /**
     * 核心贪心逻辑：
     * 给定等待天数 days，判断能否制作出 m 束花
     */
    private boolean check(int days, int[] bloomDay, int m, int k) {
        int bouquets = 0; // 已经做好的花束
        int flowers = 0;  // 当前连续可用的花朵数

        for (int bloom : bloomDay) {
            // 如果这朵花在等待天数内开了
            if (bloom <= days) {
                flowers++;
                // 如果凑够了 k 朵连续的花，就做成一束
                if (flowers == k) {
                    bouquets++;
                    flowers = 0; // 归零，重新开始凑下一束
                }
            } else {
                // 花没开，连续性中断，计数器清零
                flowers = 0;
            }
        }
        // 判断凑出来的花束够不够 m 个
        return bouquets >= m;
    }
}

同类题型

视频讲解