题目描述
题目描述
题解
题解
提交记录
提交记录
中等

给你一个长度为 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 <= 105
  • 1 <= nums[i] <= 109
 
代码
代码
测试用例
测试用例
测试结果
测试结果