LeetCode 题解工作台
使数组中所有元素相等的最小开销
给你一个整数数组 nums 和两个整数 cost1 和 cost2 。你可以执行以下 任一 操作 任意 次： 从 nums 中选择下标 i 并且将 nums[i] 增加 1 ，开销为 cost1 。 选择 nums 中两个 不同 下标 i 和 j ，并且将 nums[i] 和 nums[j] 都 增…
3
题型
0
代码语言
3
相关题
当前训练重点
困难 · 贪心·invariant
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个整数数组 nums 和两个整数 cost1 和 cost2 。你可以执行以下 任一 操作 任意 次：
- 从
nums中选择下标i并且将nums[i]增加1，开销为cost1。 - 选择
nums中两个 不同 下标i和j，并且将nums[i]和nums[j]都 增加1，开销为cost2。
你的目标是使数组中所有元素都 相等 ，请你返回需要的 最小开销 之和。
由于答案可能会很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [4,1], cost1 = 5, cost2 = 2
输出：15
解释：
执行以下操作可以使数组中所有元素相等：
- 将
nums[1]增加 1 ，开销为 5 ，nums变为[4,2]。 - 将
nums[1]增加 1 ，开销为 5 ，nums变为[4,3]。 - 将
nums[1]增加 1 ，开销为 5 ，nums变为[4,4]。
总开销为 15 。
示例 2：
输入：nums = [2,3,3,3,5], cost1 = 2, cost2 = 1
输出：6
解释：
执行以下操作可以使数组中所有元素相等：
- 将
nums[0]和nums[1]同时增加 1 ，开销为 1 ，nums变为[3,4,3,3,5]。 - 将
nums[0]和nums[2]同时增加 1 ，开销为 1 ，nums变为[4,4,4,3,5]。 - 将
nums[0]和nums[3]同时增加 1 ，开销为 1 ，nums变为[5,4,4,4,5]。 - 将
nums[1]和nums[2]同时增加 1 ，开销为 1 ，nums变为[5,5,5,4,5]。 - 将
nums[3]增加 1 ，开销为 2 ，nums变为[5,5,5,5,5]。
总开销为 6 。
示例 3：
输入：nums = [3,5,3], cost1 = 1, cost2 = 3
输出：4
解释：
执行以下操作可以使数组中所有元素相等：
- 将
nums[0]增加 1 ，开销为 1 ，nums变为[4,5,3]。 - 将
nums[0]增加 1 ，开销为 1 ，nums变为[5,5,3]。 - 将
nums[2]增加 1 ，开销为 1 ，nums变为[5,5,4]。 - 将
nums[2]增加 1 ，开销为 1 ，nums变为[5,5,5]。
总开销为 4 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1061 <= cost1 <= 1061 <= cost2 <= 106
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is dominated by sorting and evaluating each candidate target, roughly O(n log n) for sorting plus O(n) for prefix sum evaluation. Space complexity is O(n) for storing prefix sums and intermediate calculations. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may ask if your approach always finds the minimal cost or if edge cases could violate the greedy assumption.
- question_mark
Expect questions on optimizing calculations for large arrays to avoid TLE with naive nested loops.
- question_mark
Clarify how prefix sums and invariants interact to maintain correctness while reducing runtime.
常见陷阱
外企场景- error
Failing to consider both operation costs correctly when computing conversion costs for each element.
- error
Neglecting modulo 10^9 + 7 leading to integer overflow in languages with fixed-size integers.
- error
Assuming the array's median is always optimal without verifying against operation cost differences.
进阶变体
外企场景- arrow_right_alt
Minimizing cost when each element has a distinct cost function for increments and decrements.
- arrow_right_alt
Extending the problem to two-dimensional grids where each cell can be equalized with row and column operations.
- arrow_right_alt
Calculating minimum cost with fractional increments or continuous values rather than integer steps.