没多难
还是写很久
上班后真的变笨了
3013. Divide an Array Into Subarrays With Minimum Cost II
按照题目, 第一个subarray的cost永远是 nums[0]
所以要考虑的只有后面k-1个subarray的cost
那就用sliding window
一开始的范围就是1 ~ 1 + dist
找出window内最小的k-1个数
这边可以用maxHeap来记录这k-1个数
并且用minHeap纪录范围内不在maxHeap的数
就这样维护maxHeap就可以找到答案了
golang code :
type node struct {
val int
idx int // 记录在 heap 阵列中的索引
whichHeap int // 0 为 MinHeap, 1 为 MaxHeap (自定义标记)
}
type GeneralHeap struct {
nodes []*node
isMax bool // true 为 MaxHeap, false 为 MinHeap
}
func (h GeneralHeap) Len() int { return len(h.nodes) }
func (h GeneralHeap) Swap(i, j int) {
h.nodes[i], h.nodes[j] = h.nodes[j], h.nodes[i]
// 关键：交换时同步更新 node 内部的 idx
h.nodes[i].idx = i
h.nodes[j].idx = j
}
func (h GeneralHeap) Less(i, j int) bool {
if h.isMax {
return h.nodes[i].val > h.nodes[j].val
}
return h.nodes[i].val < h.nodes[j].val
}
func (h *GeneralHeap) Push(x interface{}) {
n := x.(*node)
n.idx = len(h.nodes)
h.nodes = append(h.nodes, n)
}
func (h *GeneralHeap) Pop() interface{} {
n := h.Len()
res := (*h).nodes[n-1]
res.idx = -1 // 代表已不在 heap 中
h.nodes = h.nodes[:n-1]
return res
}
func minimumCost(nums []int, k int, dist int) int64 {
n := len(nums)
maxH := GeneralHeap{make([]*node, 0), true}
minH := GeneralHeap{make([]*node, 0), false}
ans, curSum := math.MaxInt64, 0
nodeRec := make([]*node, n)
targetSize := k - 1
for i := 0; i < n; i++ {
nodeRec[i] = &node{nums[i], -1, -1}
}
add := func(nd *node) {
heap.Push(&maxH, nd)
nd.whichHeap = 1
curSum += nd.val
if maxH.Len() > targetSize {
top := heap.Pop(&maxH).(*node)
top.whichHeap = 0
curSum -= top.val
heap.Push(&minH, top)
}
}
remove := func(nd *node) {
if nd.whichHeap == 0 {
heap.Remove(&minH, nd.idx)
} else if nd.whichHeap == 1 {
curSum -= nd.val
heap.Remove(&maxH, nd.idx)
if minH.Len() > 0 {
top := heap.Pop(&minH).(*node)
top.whichHeap = 1
curSum += top.val
heap.Push(&maxH, top)
}
}
nd.whichHeap = -1
}
for i := 1; i <= 1+dist && i < n; i++ {
add(nodeRec[i])
}
ans = curSum
for i := 1; i < n; i++ {
remove(nodeRec[i])
right := 1 + dist + i
if right < n {
add(nodeRec[right])
}
if maxH.Len() == targetSize {
ans = min(ans, curSum)
}
}
return int64(ans + nums[0])
}

为什么你那么强