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

福大大架构师每日一题

发布于 2024-06-07 18:31:20

800

发布于 2024-06-07 18:31:20

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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))
}