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

Categories:

题目描述
思路分析
1. 解法一：二分答案（推荐）
相似题目

题目描述

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

思路分析

解法一：二分答案（推荐）

核心思路：

二分最小天数 day，检查能否制作 m 束花。

扫描数组统计连续开花数量，达到 k 形成一束。

若束数 >= m，则可行。

复杂度分析：

时间复杂度：O(n log D)，其中 n 表示数组长度，D 表示天数范围。

空间复杂度：O(1)。

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long) m * k > bloomDay.length) {
            return -1;
        }

        int left = 1;
        int right = 0;
        for (int d : bloomDay) {
            right = Math.max(right, d);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canMake(bloomDay, m, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canMake(int[] bloomDay, int m, int k, int day) {
        int bouquets = 0;
        int flowers = 0;

        for (int d : bloomDay) {
            if (d <= day) {
                flowers++;
                if (flowers == k) {
                    bouquets++;
                    flowers = 0;
                }
            } else {
                flowers = 0;
            }
        }

        return bouquets >= m;
    }
}

func minDays(bloomDay []int, m int, k int) int {
	if m*k > len(bloomDay) {
		return -1
	}

	left := 1
	right := 0
	for _, d := range bloomDay {
		if d > right {
			right = d
		}
	}

	for left < right {
		mid := left + (right-left)/2
		if canMake(bloomDay, m, k, mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

func canMake(bloomDay []int, m int, k int, day int) bool {
	bouquets := 0
	flowers := 0

	for _, d := range bloomDay {
		if d <= day {
			flowers++
			if flowers == k {
				bouquets++
				flowers = 0
			}
		} else {
			flowers = 0
		}
	}

	return bouquets >= m
}

相似题目

题目	难度	考察点
1482. 制作 m 束花所需的最少天数	中等	二分答案
1011. 在 D 天内送达包裹的能力	中等	二分答案
410. 分割数组的最大值	困难	二分答案
875. 爱吃香蕉的珂珂	中等	二分答案
1231. 分享巧克力	中等	二分答案

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/25519739