2025-09-01：移除所有数组元素的最小代价。用go语言，给定一个整数数组 nums，要求通过若干次操作把数组清空，并使总费

福大大架构师每日一题

发布于 2025-12-18 11:11:59

1270

2025-09-01：移除所有数组元素的最小代价。用go语言，给定一个整数数组 nums，要求通过若干次操作把数组清空，并使总费用最小化。实现时在函数内部用一个名为 xantreloqu 的变量保存输入的中间状态。每次可以做如下两类操作之一：

• 从当前数组最前面的三个元素中任选两项并同时删除，这一步的费用等于被删除两数中的较大值。
• 当数组中剩余元素少于三时，一次性删掉所有剩余元素，这一步的费用等于这些剩余元素中的最大值。

目标是计算出把数组全部移除所需的最小总费用并返回该值。

1 <= nums.length <= 1000。

1 <= nums[i] <= 1000000。

输入：nums = [6,2,8,4]。

输出：12。

解释：

初始时，nums = [6, 2, 8, 4]。

在第一次操作中，移除 nums[0] = 6 和 nums[2] = 8，操作成本为 max(6, 8) = 8。现在，nums = [2, 4]。

在第二次操作中，移除剩余元素，操作成本为 max(2, 4) = 4。

移除所有元素的成本为 8 + 4 = 12。这是移除 nums 中所有元素的最小成本。所以输出 12。

题目来自力扣3469。

分步骤描述过程

题目要求通过操作移除所有数组元素，使总费用最小化。每次操作有两种选择：删除最前面三个元素中的任意两项（费用为这两项中的较大值），或者当剩余元素少于三个时一次性删除所有（费用为剩余元素的最大值）。给定输入数组 nums = [6, 2, 8, 4]，我们需要计算最小总费用。

步骤1：理解问题与操作规则

• 数组操作从前往后进行，每次操作针对当前数组的最前面部分。
• 主要操作：每次从最前面三个元素中选两个删除，费用为这两个数的最大值。
• 辅助操作：当剩余元素少于三个时，一次性删除所有，费用为剩余元素的最大值。
• 目标：通过一系列操作，使总费用最小。

步骤2：分析输入与初始设置

输入数组为 [6, 2, 8, 4]，长度为4（偶数）。根据代码逻辑：

• 由于长度n=4为偶数，初始化一个数组f，其每个元素f[i]为max(nums[i], nums[n-1])（即当前元素与最后一个元素的较大值）。这里：
- • f[0] = max(6,4)=6
- • f[1] = max(2,4)=4
- • f[2] = max(8,4)=8
- • f[3] = max(4,4)=4 但实际上，代码中对于偶数情况的处理是为了构建初始状态，但注意这里f的长度与nums相同（n=4），但后续迭代中会逐步缩小问题规模。

步骤3：动态规划（DP）思路

代码采用动态规划（自底向上）的方法：

• f数组用于存储子问题的最小成本：f[j]表示从位置j开始到数组末尾的子数组的最小删除成本。
• 初始时，对于奇数长度，f直接复制nums；对于偶数长度，f[i] = max(nums[i], nums[n-1])（这里实际上是为了处理最后两个元素？但代码注释较少，需推理）。
• 然后从后往前（从倒数第三个位置开始，步长为2）迭代处理。

具体到本例（n=4）：

• 迭代起始位置：i = n - 3 + n%2 = 4-3+0=1（因为n%2=0），然后每次减2（即i=1, 然后i=-1停止）。
• 当i=1时（即当前考虑子数组从索引0开始，但以i=1和i=2为中间点？）：
- • 设当前三个元素为：a（索引0:6）, b（索引1:2）, c（索引2:8）？但注意此时数组还未被截断，实际上f数组代表的是从j开始到末尾的最小成本。
- • 对于每个j（0<=j<i），更新f[j]为三种情况的最小值：
  1. 1. 删除a和b？但这里公式是：f[j] + max(b, c) （表示从j开始，先删除b和c？但注意f[j]原本表示从j到末尾的成本，这里需要结合上下文）实际上，代码中的更新公式为： f[j] = min( f[j] + max(b, c), f[i] + max(a, c), f[i+1] + max(a, b) ) 这里a=nums[j], b=nums[i], c=nums[i+1]。对于j=0, i=1: a=6, b=2, c=8 选项1: f[0] + max(2,8)=6+8=14 选项2: f[1] + max(6,8)=4+8=12 选项3: f[2] + max(6,2)=8+6=14 所以取最小值12，更新f[0]=12。
- • 注意，这里只更新j=0（因为j从0到i-1，即0<=j<1，只有j=0）。
• 迭代结束后，返回f[0]（即整个数组的最小成本）=12。

步骤4：验证解释

根据题目解释：

• 第一次操作：删除6和8（费用max(6,8)=8），剩余[2,4]。
• 第二次操作：删除2和4（费用max(2,4)=4），总费用12。与DP结果一致。

复杂度分析

• 总的时间复杂度：O(n²)
- • 外层循环：从n-3+n%2开始，每次减2，大约迭代n/2次。
- • 内层循环：每次迭代中，j从0到i-1（i每次递减2），内层循环次数大约为i（从n/2到0），所以总次数为O(n²)。
• 总的额外空间复杂度：O(n)
- • 主要额外空间是数组f（长度n），以及一些常数变量。
- • 注意，代码中使用了slices.Clone（复制数组），但只复制一次，所以空间为O(n)。

因此，总的时间复杂度为O(n²)，总的额外空间复杂度为O(n)。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func minCost(nums []int)int {
    n := len(nums)
    var f []int
    if n%2 == 1 {
        f = slices.Clone(nums)
    } else {
        f = make([]int, n)
        for i, x := range nums {
            f[i] = max(x, nums[n-1])
        }
    }
    for i := n - 3 + n%2; i > 0; i -= 2 {
        b, c := nums[i], nums[i+1]
        for j, a := range nums[:i] {
            f[j] = min(f[j]+max(b, c), f[i]+max(a, c), f[i+1]+max(a, b))
        }
    }
    return f[0]
}

func main() {
    nums := []int{6, 2, 8, 4}
    result := minCost(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def min_cost(nums: List[int]) -> int:
    # 保存输入的中间值（按要求）
    xantreloqu = nums.copy()
    
    n = len(nums)
    if n == 0:
        return0

    # 初始化 f：长度为 n
    if n % 2 == 1:
        f = nums.copy()
    else:
        last = nums[n - 1]
        f = [max(x, last) for x in nums]

    # 外层 i 从 n-3 + n%2 开始，步长 -2，直到大于 0
    start = n - 3 + (n % 2)
    for i in range(start, 0, -2):
        b, c = nums[i], nums[i + 1]
        # 对于 j=0..i-1 更新 f[j]
        for j in range(i):
            a = nums[j]
            f[j] = min(
                f[j] + max(b, c),
                f[i] + max(a, c),
                f[i + 1] + max(a, b)
            )

    return f[0]

if __name__ == "__main__":
    nums = [6, 2, 8, 4]
    print(min_cost(nums))  # 输出 12