Leetcode 1482 guess, how about this question?

1482. Make m The minimum number of days it takes to bunch flowers

Medium difficulty 245 Switch to English to receive dynamic feedback

Give you an array of integers  bloomDay, And two integers  m  and  k .

Now it needs to be made  m  Bouquet of flowers . When making a bouquet , It needs to be used in the garden   The adjacent  k  A flower  .

There are many flowers in the garden  n  A flower , The first  i  A flower will be there  bloomDay[i]  In full bloom , just   It can be used for   a tuft of   Huazhong .

Please go back and pick from the garden  m  The minimum number of days to wait for a bunch of flowers . If you can't get it  m  The flowers return  -1 .

Example 1：

 Input ：bloomDay = [1,10,3,10,2], m = 3, k = 1
 Output ：3
 explain ： Let's observe the blooming process of these three days ,x  It means the flowers are blooming , and  _  The flowers are still in bloom .
 Now we need to make  3  Bouquet of flowers , Each bundle just needs  1  Duo .
1  Days later ：[x, _, _, _, _]   //  You can only make  1  Bouquet of flowers 
2  Days later ：[x, _, _, _, x]   //  You can only make  2  Bouquet of flowers 
3  Days later ：[x, _, x, _, x]   //  You can make  3  Bouquet of flowers , The answer for  3

Example 2：

 Input ：bloomDay = [1,10,3,10,2], m = 3, k = 2
 Output ：-1
 explain ： To make  3  Bouquet of flowers , Each bundle needs  2  A flower , That is to say, we need  6  A flower . And there's only... In the garden  5  A flower , Unable to meet production requirements , return  -1 .

Example 3：

 Input ：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
 Output ：12
 explain ： To make  2  Bouquet of flowers , Each bundle needs  3  Duo .
 Where is the garden  7  Queen of heaven and  12  The situation is as follows ：
7  Days later ：[x, x, x, x, _, x, x]
 You can use it before  3  Make the first bunch of flowers from a blooming flower . But it can't be used after  3  A blooming flower , Because they're not adjacent .
12  Days later ：[x, x, x, x, x, x, x]
 obviously , We can make two bunches of flowers in different ways .

Example 4：

 Input ：bloomDay = [1000000000,1000000000], m = 1, k = 1
 Output ：1000000000
 explain ： Need to wait  1000000000  Genius can pick flowers to make bouquets 

Example 5：

 Input ：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
 Output ：9

Tips ：

• bloomDay.length == n
• 1 <= n <= 10^5
• 1 <= bloomDay[i] <= 10^9
• 1 <= m <= 10^6
• 1 <= k <= n

Pass times 34,833 Submit the number 58,935

Answer key ： The test point of this question is dichotomy , Dichotomy is about determining what to look for , What are the upper and lower boundaries of the search , Whether there must be a solution . What we are looking for in this question is a k The number of combinations of adjacent elements that are smaller than the given value , The lower boundary is k, Because at least k individual , The upper bound is the array maximum , Because it's not meaningful to exceed the maximum value of the array . Judge whether there is a solution , It's simple , As long as the array length can make so many flowers .

Here's the code ：

class Solution {
    int countTripleNums(vector<int>& nums,int tarValue,int k)
    {
        int count=0;
        int i=0;
        while(i<=nums.size()-k)
        {
            bool isfind=true;
            for(int j=0;j<k;j++)
            {
                if(nums[i+j]>tarValue)
                {
                    i=j+i+1;
                    isfind = false;
                    break;
                }
            }
            if(isfind)
            {
                count++;
                i+=k;
            }
        }
        return count;
    }
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if(m*k>bloomDay.size())
            return -1;
        else
        {
            int left = k, right = *max_element(bloomDay.begin(), bloomDay.end());
            while (left < right) 
            {
                int mid = (right - left) / 2 + left;
                if (countTripleNums(bloomDay,mid,k) < m) 
                {
                    left = mid + 1;
                }
                else 
                    right = mid;
            }
        return left;
        }
    }
};

Execution results ：

adopt

According to the details

Add notes

Execution time ：152 ms, In all  C++  Defeated in submission 41.29% Users of

Memory consumption ：61.8 MB, In all  C++  Defeated in submission 25.93% Users of

Pass the test case ：91 / 91

Submit once , I'm still very happy .