Kimi k2.6 LeetCode 2234.花园的最大总美丽值 Go实现

这是 LeetCode 2234. 花园的最大总美丽值 的 Go 实现。---核心思路回顾1. 预处理将所有 flowers[i] target 的截断到 target计算假设全部种满后的剩余花数 left2. 特判如果所有花园本来已 ≥ target或可以全部种满直接返回3. 排序后逆向枚举后缀 [i, n-1] 种满到 target前缀 [0, i-1] 用双指针求最大最小值---Go 代码gopackage mainimport (sort)func maximumBeauty(flowers []int, newFlowers int64, target int, full int, partial int) int64 {n : len(flowers)// 预处理截断到 target并计算假设全部种满后的剩余花数left : newFlowers - int64(n)*int64(target)for i : 0; i n; i {if flowers[i] target {flowers[i] target}left int64(flowers[i])}// 所有花园本来就已经 targetif left newFlowers {return int64(n) * int64(full)}// 可以全部种满if left 0 {allFull : int64(n) * int64(full)almostFull : int64(n-1)*int64(full) int64(target-1)*int64(partial)if allFull almostFull {return allFull}return almostFull}sort.Ints(flowers)var res int64 0var preSum int64 0j : 0// 枚举 i后缀 [i, n-1] 种满到 target完善花园有 n-i 个for i : 1; i n; i {// 撤销 flowers[i-1] 的种满操作把它还回前缀left int64(target - flowers[i-1])// 剩余花数为负说明连这个后缀都种不满跳过if left 0 {continue}// 双指针扩展 j看前 j 个花园能否被提升到同一水平for j i int64(flowers[j])*int64(j) preSumleft {preSum int64(flowers[j])j}// 前 j 个花园的最大最小值一定 target因为上面特判了avg : (left preSum) / int64(j)totalBeauty : avg*int64(partial) int64(n-i)*int64(full)if totalBeauty res {res totalBeauty}}return res}---复杂度分析项目 复杂度时间 O(n log n) — 排序主导枚举 双指针 O(n)空间 O(1) 额外空间原地排序---关键点说明要点 说明left 的含义 假设全部种满到 target 后剩余的花数可能为负逆向枚举 从 i1 开始逐步把 flowers[i-1] 从完善花园移回不完善前缀双指针 j 只增不减维护前缀中可以被提升到同一水平的最小花园数量avg 计算 (left preSum) / j 表示前 j 个花园能被提升到的最大共同最小值全满特判 即使能全满也要比较留一个到 target-1是否更优partial 可能很大 参考[灵茶山艾府题解](https://leetcode.cn/problems/maximum-total-beauty-of-the-gardens/solutions/1408882/)