2024-06-01：用go语言，给定一个从0开始索引的整数数组 nums 、两个正整数 k 和 dist 。 数组的代价是该数

2024-06-01：用go语言，给定一个从0开始索引的整数数组 nums 、两个正整数 k 和 dist 。

数组的代价是该数组中的第一个元素。

问题要求将数组 nums 分割成 k 个连续且不重叠的子数组，

同时确保第二个到第k个子数组的第一个元素与它前面的子数组的最后一个元素的距离不超过 dist 。

换句话说，要把数组分割成这样的子数组：

nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)]，

并且满足 ik-1 - i1 <= dist 。

问题的目标是求得这些子数组的代价之和的最小值。

输入：nums = [1,3,2,6,4,2], k = 3, dist = 3。

输出：5。

答案2024-06-01：

chatgpt

题目来自leetcode3013。

大体步骤如下：

1.创建两个堆结构l和r，其中l是最大堆，r是最小堆，所有元素取反存储。这两个堆用于维持子数组之间的距离。

2.初始化堆l和r，将数组nums的一部分元素（前dist+2个）依次加入堆l中。

3.对堆l进行调整，保持其大小不超过k，如果超过则将多出的部分元素从堆l移至堆r中。

4.遍历数组nums，从第dist+2个元素开始，进行子数组的调整：

• 移除out元素，根据其大小从堆l或堆r中移除。

• 添加in元素，根据其大小添加到堆l或堆r中。

• 维护堆的大小，保持堆l的大小在k-1和k+1之间。

• 计算当前的代价和mn，并更新为当前的最小值。

5.最后返回数组的第一个元素与最小代价和mn的和作为最终结果。

总的时间复杂度分析：

• 初始化堆的时间复杂度为 O(dist).

• 遍历数组的时间复杂度为 O(n), 其中对堆的操作的时间复杂度为 O(log k). 因此，总的时间复杂度为 O(n * log k).

总的额外空间复杂度分析：

• 除了输入参数外，算法使用了两个堆结构及相关变量来维护子数组的信息。

• 堆结构的空间复杂度为 O(k)。

• 因此，总的额外空间复杂度为 O(k).

Go完整代码如下：

package main

import (

"container/heap"

"fmt"

"sort"

)

func minimumCost(nums []int, k int, dist int) int64 {

k--

l := &lazyHeap{todo: map[int]int{}} // 最大堆

r := &lazyHeap{todo: map[int]int{}} // 最小堆，所有元素取反

for _, x := range nums[1 : dist+2] {

l.push(x)

}

for l.size > k {

r.push(-l.pop())

}

mn := l.sum

for i := dist + 2; i < len(nums); i++ {

// 移除 out

out := nums[i-dist-1]

if out <= l.top() {

l.del(out)

} else {

r.del(-out)

}

// 添加 in

in := nums[i]

if in < l.top() {

l.push(in)

} else {

r.push(-in)

}

// 维护大小

if l.size == k-1 {

l.push(-r.pop())

} else if l.size == k+1 {

r.push(-l.pop())

}

mn = min(mn, l.sum)

}

return int64(nums[0] + mn)

}

type lazyHeap struct {

sort.IntSlice

todo map[int]int

size int // 实际大小

sum  int // 实际元素和

}

func (h lazyHeap) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] } // 最大堆

func (h *lazyHeap) Push(v any)        { h.IntSlice = append(h.IntSlice, v.(int)) }

func (h *lazyHeap) Pop() any          { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

func (h *lazyHeap) del(v int)         { h.todo[v]++; h.size--; h.sum -= v } // 懒删除

func (h *lazyHeap) push(v int) {

if h.todo[v] > 0 {

h.todo[v]--

} else {

heap.Push(h, v)

}

h.size++

h.sum += v

}

func (h *lazyHeap) pop() int { h.do(); h.size--; v := heap.Pop(h).(int); h.sum -= v; return v }

func (h *lazyHeap) top() int { h.do(); return h.IntSlice[0] }

func (h *lazyHeap) do() {

for h.Len() > 0 && h.todo[h.IntSlice[0]] > 0 {

h.todo[h.IntSlice[0]]--

heap.Pop(h)

}

}

func main() {

nums := []int{1, 3, 2, 6, 4, 2}

fmt.Println(minimumCost(nums, 3, 3))

}

在这里插入图片描述