元宝 LeetCode 3139. 使数组中所有元素相等的最小开销 Java实现

LeetCode 3139 · Minimum Cost to Equalize Array — Java 解法

题意：只能对数组元素做 +1 操作——单点 +1 花费cost1，两点同时 +1 花费cost2。目标使所有元素相等，求最小总花费（对 1e9+7 取模）。

核心思路：

• 目标值 ≥ 原数组最大值（只能增不能减），枚举目标target ∈ [maxNum, 2*maxNum)即可找到最优解。

• 设totalGap = target*n - sum(nums)（总需增加的次数），maxGap = target - minNum（单个元素最多需增加的次数）。

• 双增操作最多配对pairs = min(totalGap/2, totalGap - maxGap)，其余用单增补齐。

• 若cost1*2 ≤ cost2或n < 3，双增不划算，直接全用单增把数组升到maxNum。

class Solution { public int minCostToEqualizeArray(int[] nums, int cost1, int cost2) { final int MOD = 1_000_000_007; final int n = nums.length; int minNum = nums[0], maxNum = nums[0]; long sum = 0; for (int v : nums) { if (v < minNum) minNum = v; if (v > maxNum) maxNum = v; sum += v; } // 只用单增操作就够了 if (cost1 * 2L <= cost2 || n < 3) { long totalGap = 1L * maxNum * n - sum; return (int) ((cost1 * (totalGap % MOD)) % MOD); } long ans = Long.MAX_VALUE; // 枚举目标值 for (int target = maxNum; target < 2 * maxNum; target++) { long totalGap = 1L * target * n - sum; long maxGap = target - minNum; // 最多能配对的双增操作次数 long pairs = Math.min(totalGap / 2, totalGap - maxGap); long cost = cost1 * (totalGap - 2 * pairs) + cost2 * pairs; if (cost < ans) ans = cost; } return (int) (ans % MOD); } }

复杂度：遍历O(maxNum)≤O(1e6)，数组扫描O(n)，空间O(1)。

如需我补充关键结论推导或 Python 版本也可以说～