Re: [閒聊] 每日leetcode

[JKWP (神楽めあ的煙灰缸)]

沒多難

還是寫很久

上班後真的變笨了

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://www.ptt.cc/bbs/Marginalman/M.1770042256.A.907.html
→ oin1104: 為什麼你那麼強