What pattern does Maximum Total Beauty of the Gardens primarily use?

This problem relies on binary search over the valid answer space combined with sorting and prefix sums to efficiently determine feasible minimum flower levels.

How do I decide which gardens to make complete first?

Sort gardens by current flowers and prioritize adding flowers to the smallest incomplete gardens to reach target, while tracking newFlowers usage.

Can all gardens become complete and still maximize beauty?

Not always; sometimes leaving a few gardens below target yields higher total beauty due to the partial contribution formula.

What is the time complexity of this solution?

Sorting is O(n log n) and binary search over flower levels runs in O(log(max(target, flowers))) with O(n) feasibility checks, giving overall O(n log n + n log target).

What is a common mistake when implementing this problem?

A frequent error is ignoring the partial beauty for incomplete gardens or miscalculating the minimum flower count when distributing new flowers.

#2234

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

花园的最大总美丽值

Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花不能移走。同时给你 newFlowers ，表示 Alice 额外可以种花的…

数组双指针二分查找贪心排序

题目描述

Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。

给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花不能移走。同时给你 newFlowers ，表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target ，full 和 partial 。

如果一个花园有至少 target 朵花，那么这个花园称为 完善的 ，花园的 总美丽值 为以下分数之和：

完善花园数目乘以 full.
剩余 不完善 花园里，花的 最少数目 乘以 partial 。如果没有不完善花园，那么这一部分的值为 0 。

请你返回 Alice 种最多 newFlowers 朵花以后，能得到的最大总美丽值。

示例 1：

输入：flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
输出：14
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 2 朵花
- 在第 1 个花园种 3 朵花
- 在第 2 个花园种 1 朵花
- 在第 3 个花园种 1 朵花
花园里花的数目为 [3,6,2,2] 。总共种了 2 + 3 + 1 + 1 = 7 朵花。
只有 1 个花园是完善的。
不完善花园里花的最少数目是 2 。
所以总美丽值为 1 * 12 + 2 * 1 = 12 + 2 = 14 。
没有其他方案可以让花园总美丽值超过 14 。

示例 2：

输入：flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
输出：30
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 3 朵花
- 在第 1 个花园种 0 朵花
- 在第 2 个花园种 0 朵花
- 在第 3 个花园种 2 朵花
花园里花的数目为 [5,4,5,5] 。总共种了 3 + 0 + 0 + 2 = 5 朵花。
有 3 个花园是完善的。
不完善花园里花的最少数目为 4 。
所以总美丽值为 3 * 2 + 4 * 6 = 6 + 24 = 30 。
没有其他方案可以让花园总美丽值超过 30 。
注意，Alice可以让所有花园都变成完善的，但这样她的总美丽值反而更小。

提示：

1 <= flowers.length <= 10⁵
1 <= flowers[i], target <= 10⁵
1 <= newFlowers <= 10¹⁰
1 <= full, partial <= 10⁵

lightbulb

解题思路

方法一：枚举 + 二分查找

我们注意到，如果一个花园中种的花的数目已经大于等于 $\textit{target}$ ，那么这个花园就已经是完善的花园，不能再改变。而不完善的花园中，可以通过种更多的花来使得这个花园变成完善的花园。

我们不妨枚举有多少个花园最终成为完善的花园，假设初始时有 $x$ 个完善的花园，那么我们可以在 $[x, n]$ 范围内枚举。我们应该选择哪些不完善花园变成完善花园呢？实际上，我们应该选择那么花的数目较多的花园，这样才能使得最终剩下的可额外种植的花更多，将这些花用于提升不完善花园的最小值。因此，我们对数组 $\textit{flowers}$ 进行排序。

接下来，我们枚举完善花园的数目 $x$ ，那么当前要变成完善花园的是 $\textit{target}[n-x]$ ，需要种植的花的数量为 $\max(0, \textit{target} - \textit{flowers}[n - x])$ 。

我们更新剩余可种植的花 $\textit{newFlowers}$ ，如果小于 $0$ ，说明已经不能将更多的花园变成完善花园了，直接退出枚举。

否则，我们在 $[0,..n-x-1]$ 范围内，二分查找可以把不完善花园变成完善花园的最大下标。记下标为 $l$ ，那么所需要种植的花的数量为 $\textit{cost} = \textit{flowers}[l] \times (l + 1) - s[l + 1]$ ，其中 $s[i]$ 是 $\textit{flowers}$ 数组中前 $i$ 个数之和。如果此时还能提升最小值的大小，我们算出能提升的幅度 $\frac{\textit{newFlowers} - \textit{cost}}{l + 1}$ ，并且保证最终的最小值不超过 $\textit{target}-1$ 。即最小值 $y = \min(\textit{flowers}[l] + \frac{\textit{newFlowers} - \textit{cost}}{l + 1}, \textit{target} - 1)$ 。那么此时花园的美丽值为 $x \times \textit{full} + y \times \textit{partial}$ 。答案为所有美丽值的最大值。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{flowers}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def maximumBeauty(
        self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int
    ) -> int:
        flowers.sort()
        n = len(flowers)
        s = list(accumulate(flowers, initial=0))
        ans, i = 0, n - bisect_left(flowers, target)
        for x in range(i, n + 1):
            newFlowers -= 0 if x == 0 else max(target - flowers[n - x], 0)
            if newFlowers < 0:
                break
            l, r = 0, n - x - 1
            while l < r:
                mid = (l + r + 1) >> 1
                if flowers[mid] * (mid + 1) - s[mid + 1] <= newFlowers:
                    l = mid
                else:
                    r = mid - 1
            y = 0
            if r != -1:
                cost = flowers[l] * (l + 1) - s[l + 1]
                y = min(flowers[l] + (newFlowers - cost) // (l + 1), target - 1)
            ans = max(ans, x * full + y * partial)
        return ans

speed

复杂度分析

指标	值
时间	complexity is dominated by sorting O(n log n) and binary search over flower levels, with O(n) per feasibility check using prefix sums. Space complexity is O(n) for storing sorted gardens and prefix sums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask how to efficiently decide which gardens to make complete when newFlowers is limited.
question_mark
Look for recognition that sorting plus prefix sums can quickly compute required flowers for minimum incomplete gardens.
question_mark
Probe whether candidate minimum levels can be efficiently tested via binary search over the answer space.

warning

常见陷阱

外企场景

error
Failing to account for the minimum flower count among incomplete gardens when calculating partial beauty.
error
Trying to brute-force all combinations of flower distributions instead of using binary search over the valid answer space.
error
Neglecting to handle edge cases where all gardens can become complete or when no additional flowers are available.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximizing beauty when full and partial values vary dynamically for each garden.
arrow_right_alt
Considering additional constraints where some gardens cannot receive more flowers.
arrow_right_alt
Finding the number of planting ways that achieve the maximum total beauty rather than the value itself.

help

常见问题

外企场景

继续练习

#2271 毯子覆盖的最多白色砖块数 #2071 你可以安排的最多任务数目 #2406 将区间分为最少组数