写点什么

【LeetCode】制作 m 束花所需的最少天数 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 05 月 09 日

题目描述

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


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


花园中有 n 朵花,第 i 朵花会在 bloomDay[i] 时盛开,恰好 可以用于 一束 花中。


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


示例 1:
输入:bloomDay = [1,10,3,10,2], m = 3, k = 1输出:3解释:让我们一起观察这三天的花开过程,x 表示花开,而 _ 表示花还未开。现在需要制作 3 束花,每束只需要 1 朵。1 天后:[x, _, _, _, _] // 只能制作 1 束花2 天后:[x, _, _, _, x] // 只能制作 2 束花3 天后:[x, _, x, _, x] // 可以制作 3 束花,答案为 3
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天是母亲节,每日一题很应景,祝大家节日快乐。

  • 这个题目有一定的难度,拆分成两个小函数,一个函数用来判断某天是否能达到相应的花束,一个函数用来找天数最小值。

  • 二分查找可以用来查找最小天数。

AC 代码

public class DayCode {    public static void main(String[] args) {        int[] bloomDay = new int[]{1, 10, 3, 10, 2};        int m = 3;        int k = 1;        int ans = new DayCode().minDays(bloomDay, m, k);        System.out.println(ans);    }
public int minDays(int[] bloomDay, int m, int k) { int n = bloomDay.length; if (n < m * k) { return -1; } int low = Integer.MAX_VALUE; int high = 0; for (int i = 0; i < n; i++) { low = Math.min(low, bloomDay[i]); high = Math.max(high, bloomDay[i]); } while (low < high) { int days = low + (high - low) / 2; if (help(bloomDay, days, m, k)) { high = days; } else { low = days + 1; } }
return low; }
private boolean help(int[] bloomDay, int days, int m, int k) { int flowers = 0; int bouquets = 0; int n = bloomDay.length; for (int i = 0; i < n && bouquets < m; i++) { if (bloomDay[i] <= days) { flowers++; if (flowers == k) { bouquets++; flowers = 0; } } else { flowers = 0; } }
return bouquets >= m; }}
复制代码

总结

  • 上述代码的时间复杂度是 O(n * log(n)), 空间复杂度是 O(1)

  • 坚持每日一题,加油!

发布于: 2021 年 05 月 09 日阅读数: 9
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】制作 m 束花所需的最少天数Java题解