作者JKWP (神楽めあ的煙灰缸)
看板Marginalman
標題Re: [閒聊] 每日leetcode
時間Mon Feb 2 22:24:14 2026
沒多難
還是寫很久
上班後真的變笨了
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])
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Marginalman/M.1770042256.A.907.html
1F：→ oin1104: 為什麼你那麼強 02/02 22:40