![Kimi K2.6 LeetCode 2234.花园的最大总美丽值 public long maximumBeauty(int[] flowers, long newFlowers](images/news1.jpg)
这是 LeetCode 2234. 花园的最大总美丽值Maximum Total Beauty of the Gardens的详细题解。---题目大意有 n 个花园flowers[i] 表示第 i 个花园已有的花数。你可以额外种最多 newFlowers 朵花。- 完善的花园花数 ≥ target贡献 full 分。- 不完善的花园取所有不完善花园中花数的最小值 min贡献 min × partial 分。目标最大化总美丽值。---核心思路1. 预处理与特判先把所有 flowers[i] target 的截断到 target因为花数超过 target 没有意义。假设所有花园都种满到 target计算剩余花数left newFlowers - Σ(target - flowers[i])- 如果 left newFlowers说明所有花园本来就已经 ≥ target直接返回 n * full。- 如果 left 0说明可以全部种满。但可能留一个花园只种到 target-1 更优获得 partial 收益取 max(n*full, (n-1)*full (target-1)*partial)。2. 枚举 双指针如果无法全部种满将 flowers 升序排序。逆向思维先假设所有花园都种满到 target然后从左到右枚举不种满的花园前缀。- 设后缀 [i, n-1] 是完善的种满到 target共 n-i 个。- 前缀 [0, i-1] 是不完善的需要把剩余的花 left 尽量平均分配让最小值最大。用双指针维护前缀中可以被提升到同一水平的最小花园数量 j- 条件flowers[j] * j pre_sum left即剩余的花足够把前 j 个花园都提升到至少 flowers[j]。- 最大最小值avg (left pre_sum) / j整数除法。总美丽值avg * partial (n - i) * full取最大值即可。---Java 代码javaclass Solution {public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {int n flowers.length;// 预处理截断到 target并计算假设全部种满后的剩余花数long left newFlowers - 1L * n * target;for (int i 0; i n; i) {flowers[i] Math.min(flowers[i], target);left flowers[i];}// 所有花园本来就已经 targetif (left newFlowers) {return 1L * n * full;}// 可以全部种满if (left 0) {return Math.max(1L * n * full, 1L * (n - 1) * full 1L * (target - 1) * partial);}Arrays.sort(flowers);long res 0;long preSum 0;int j 0;// 枚举 i后缀 [i, n-1] 种满到 target完善花园有 n-i 个for (int i 1; i n; i) {// 撤销 flowers[i-1] 的种满操作把它还回前缀left target - flowers[i - 1];// 剩余花数为负说明连这个后缀都种不满跳过if (left 0) {continue;}// 双指针扩展 j看前 j 个花园能否被提升到同一水平while (j i 1L * flowers[j] * j preSum left) {preSum flowers[j];j;}// 前 j 个花园的最大最小值一定 target因为上面特判了long avg (left preSum) / j;long totalBeauty avg * partial 1L * (n - i) * full;res Math.max(res, totalBeauty);}return res;}}---复杂度分析项目 复杂度时间 O(n log n) — 排序主导后续枚举 双指针是 O(n)空间 O(1) — 仅使用常数额外空间排序是原地排序---关键点总结1. 逆向思维先假设全满再枚举哪些不满避免正向分配花的复杂组合。2. 双指针维护前缀j 只会向右移动配合前缀和 preSum均摊 O(n)。3. 特判全满情况如果剩余花足够全满还要比较留一个到 target-1的策略因为 partial 可能很大。 参考[灵茶山艾府题解](https://leetcode.cn/problems/maximum-total-beauty-of-the-gardens/solutions/1408882/) 及 [阿里云开发者社区](https://developer.aliyun.com/article/1424450)
Kimi K2.6 LeetCode 2234.花园的最大总美丽值 public long maximumBeauty(int[] flowers, long newFlowers
这是 LeetCode 2234. 花园的最大总美丽值Maximum Total Beauty of the Gardens的详细题解。---题目大意有 n 个花园flowers[i] 表示第 i 个花园已有的花数。你可以额外种最多 newFlowers 朵花。- 完善的花园花数 ≥ target贡献 full 分。- 不完善的花园取所有不完善花园中花数的最小值 min贡献 min × partial 分。目标最大化总美丽值。---核心思路1. 预处理与特判先把所有 flowers[i] target 的截断到 target因为花数超过 target 没有意义。假设所有花园都种满到 target计算剩余花数left newFlowers - Σ(target - flowers[i])- 如果 left newFlowers说明所有花园本来就已经 ≥ target直接返回 n * full。- 如果 left 0说明可以全部种满。但可能留一个花园只种到 target-1 更优获得 partial 收益取 max(n*full, (n-1)*full (target-1)*partial)。2. 枚举 双指针如果无法全部种满将 flowers 升序排序。逆向思维先假设所有花园都种满到 target然后从左到右枚举不种满的花园前缀。- 设后缀 [i, n-1] 是完善的种满到 target共 n-i 个。- 前缀 [0, i-1] 是不完善的需要把剩余的花 left 尽量平均分配让最小值最大。用双指针维护前缀中可以被提升到同一水平的最小花园数量 j- 条件flowers[j] * j pre_sum left即剩余的花足够把前 j 个花园都提升到至少 flowers[j]。- 最大最小值avg (left pre_sum) / j整数除法。总美丽值avg * partial (n - i) * full取最大值即可。---Java 代码javaclass Solution {public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {int n flowers.length;// 预处理截断到 target并计算假设全部种满后的剩余花数long left newFlowers - 1L * n * target;for (int i 0; i n; i) {flowers[i] Math.min(flowers[i], target);left flowers[i];}// 所有花园本来就已经 targetif (left newFlowers) {return 1L * n * full;}// 可以全部种满if (left 0) {return Math.max(1L * n * full, 1L * (n - 1) * full 1L * (target - 1) * partial);}Arrays.sort(flowers);long res 0;long preSum 0;int j 0;// 枚举 i后缀 [i, n-1] 种满到 target完善花园有 n-i 个for (int i 1; i n; i) {// 撤销 flowers[i-1] 的种满操作把它还回前缀left target - flowers[i - 1];// 剩余花数为负说明连这个后缀都种不满跳过if (left 0) {continue;}// 双指针扩展 j看前 j 个花园能否被提升到同一水平while (j i 1L * flowers[j] * j preSum left) {preSum flowers[j];j;}// 前 j 个花园的最大最小值一定 target因为上面特判了long avg (left preSum) / j;long totalBeauty avg * partial 1L * (n - i) * full;res Math.max(res, totalBeauty);}return res;}}---复杂度分析项目 复杂度时间 O(n log n) — 排序主导后续枚举 双指针是 O(n)空间 O(1) — 仅使用常数额外空间排序是原地排序---关键点总结1. 逆向思维先假设全满再枚举哪些不满避免正向分配花的复杂组合。2. 双指针维护前缀j 只会向右移动配合前缀和 preSum均摊 O(n)。3. 特判全满情况如果剩余花足够全满还要比较留一个到 target-1的策略因为 partial 可能很大。 参考[灵茶山艾府题解](https://leetcode.cn/problems/maximum-total-beauty-of-the-gardens/solutions/1408882/) 及 [阿里云开发者社区](https://developer.aliyun.com/article/1424450)
