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

LeetCode 3139 · Minimum Cost to Equalize Array — Java 解法题意只能对数组元素做 1 操作——单点 1 花费cost1两点同时 1 花费cost2。目标使所有元素相等求最小总花费对 1e97 取模。核心思路目标值 ≥ 原数组最大值只能增不能减枚举目标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 版本也可以说