中等
给你一个长度为 n 的整数数组 nums。
你可以从以下操作中 任意 选择,执行 任意 次,顺序 任意。
- 前缀操作:选择一个满足
0 < i < n - 1的下标i,将下标从 0 到i - 1的 所有 元素设为nums[i]。该操作的成本为i * nums[i]。 - 后缀操作:选择一个满足
0 < i < n - 1的下标i,将下标从i + 1到n - 1的 所有 元素设为nums[i]。该操作的成本为(n - i - 1) * nums[i]。
操作的成本根据 nums[i] 的 当前 值计算。所选前缀或后缀中的每个元素都计入成本,即使该元素已经等于 nums[i]。
返回使 nums 中 所有 元素都相等所需的 最小总成本。
示例 1:
输入: nums = [1,2,3]
输出: 4
解释:
以下是一种达到最小成本的操作序列:
| nums | 操作 | i | 修改后的 nums | 成本 |
|---|---|---|---|---|
| [1, 2, 3] | 后缀 | 1 | [1, 2, 2] | (3 - 1 - 1) * 2 = 2 |
| [1, 2, 2] | 前缀 | 1 | [2, 2, 2] | 1 * 2 = 2 |
因此,总成本为 2 + 2 = 4。
示例 2:
输入: nums = [3,3,3,6,3,3]
输出: 9
解释:
以下是一种达到最小成本的操作序列:
| nums | 操作 | i | 修改后的 nums | 成本 |
|---|---|---|---|---|
| [3, 3, 3, 6, 3, 3] | 后缀 | 2 | [3, 3, 3, 3, 3, 3] | (6 - 2 - 1) * 3 = 9 |
因此,总成本为 9。
示例 3:
输入: nums = [3,4,4,5,4,4,3]
输出: 20
解释:
以下是一种达到最小成本的操作序列:
| nums | 操作 | i | 修改后的 nums | 成本 |
|---|---|---|---|---|
| [3, 4, 4, 5, 4, 4, 3] | 前缀 | 4 | [4, 4, 4, 4, 4, 4, 3] | 4 * 4 = 16 |
| [4, 4, 4, 4, 4, 4, 3] | 后缀 | 5 | [4, 4, 4, 4, 4, 4, 4] | (7 - 5 - 1) * 4 = 4 |
因此,总成本为 16 + 4 = 20。
提示:
3 <= n == nums.length <= 1051 <= nums[i] <= 109