推荐订阅源

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

题目

给你一个整数数组 bloomDay，以及两个整数 m 和 k 。

现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。

花园中有 n 朵花，第 i 朵花会在 bloomDayi 时盛开，恰好 可以用于 一束 花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

K<=N<=10⁵
M<=10⁶

题目理解

找到数组中的m组，每组是k个相邻元素组成（组之间不能有重复），使得这些元素的最大值day最小。

题解

二分

用二分的方法，找到第一个x，使得<x的day都不能满足有m组。
所以现在要以mid为最大天数，求这样的情况下最多能有多少个分组。

时间复杂度：
外层二分：O(log2(VAL))=O(30)
内层：O(n)

    public int MinDays(int[] bloomDay, int m, int k) {
        //binary search
        int min=1000000000;
        int max=1;
        foreach(int val in bloomDay){
            min=Math.Min(min,val);
            max=Math.Max(max,val);
        }
        // Console.WriteLine(min+","+max);
        int left=min;
        int right=max;
        while(left<=right){
            int mid=(left+right)>>1;
            int groupCnt=getCnt(mid,bloomDay,k);
            if(m<=groupCnt){//[10,10]，组个数是2>目标1，但是下一次缩小范围会退出循环，所以放到这里
                //检查左侧是否能更小
                if(getCnt(mid-1,bloomDay,k)<m){
                    return mid;
                }else{
                    right=mid-1;
                }
            }else{
                left=mid+1;
            }
        }
        return -1;
    }

    private int getCnt(int max,int[] bloomDay,int k){
        int continues=0;
        int groupCnt=0;
        foreach(int val in bloomDay){
            if(val<=max){
                continues++;
                if(continues==k){
                    continues=0;
                    groupCnt++;
                }

            }else{
                continues=0;
            }
        }
        return groupCnt;
    }