Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

2818. Apply Operations to Maximize Score

這題就用遞減的monotonic stack + priority queue

算出nums每個元素的prime score

開始遍歷nums，把元素丟到monotonic stack裡面

如果monotonic stack最後一個元素的prime stack比當前的還小就pop出來

假設monotonic stack裡最後一個元素是 idx

把nums[idx]和idx是幾個subarray裡最大的prime score丟到priority queue裡面

subarray的數量就是(i-idx) * (idx-stack[(len(stack)-1)])

遍歷完後還要把monotonic stack清空並丟到priority queue裡面

最後從priority queue裡面找出前k大的數相乘就好

golang code

type node struct {
        val int
        num int
}

type maxHeap []node

func (this maxHeap) Len() int            { return len(this) }
func (this maxHeap) Less(i, j int) bool  { return this[i].val > this[j].val }
func (this maxHeap) Swap(i, j int)       { this[i], this[j] = this[j], this[i]
 }
func (this *maxHeap) Push(x interface{}) { *this = append(*this, x.(node)) }
func (this *maxHeap) Pop() interface{} {
        n := len(*this)
        res := (*this)[n-1]
        (*this) = (*this)[:n-1]
        return res
}

func maximumScore(nums []int, k int) int {
        nums = append([]int{0}, nums...)
        n, h, ans, mod, primeScores := len(nums), maxHeap{}, 1, 1_000_000_007, make(
map[int]int)
        primeScores[0] = mod
        stack := []int{0}
        for _, val := range nums {
                if _, ok := primeScores[val]; !ok {
                        primeScores[val] = findPrimeScore(val)
                }
        }
        for i := 1; i < n; i++ {
                primeScore := primeScores[nums[i]]
                for len(stack) > 0 && primeScores[nums[stack[len(stack)-1]]] < primeScore {
                        idx := stack[len(stack)-1]
                        stack = stack[:len(stack)-1]
                        l := stack[len(stack)-1]
                        heap.Push(&h, node{nums[idx], (i - idx) * (idx - l)})
                }
                stack = append(stack, i)
        }
        for len(stack) > 1 {
                idx := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                l := stack[len(stack)-1]
                heap.Push(&h, node{nums[idx], (n - idx) * (idx - l)})
        }
        for k > 0 {
                curNode := heap.Pop(&h).(node)
                exp := 0
                if k > curNode.num {
                        k -= curNode.num
                        exp = curNode.num
                } else {
                        exp = k
                        k = 0
                }
                ans = ans * modPow(curNode.val, exp, mod) % mod
        }
        return ans % mod
}
func modPow(base, exp, mod int) int {
        res := 1
        base %= mod
        for exp > 0 {
                if exp&1 == 1 {
                        res = res * base % mod
                }
                base = base * base % mod
                exp /= 2
        }
        return res
}
func findPrimeScore(n int) int {
        score := 0
        for i := 2; i*i <= n; i++ {
                if n%i == 0 {
                        for n%i == 0 {
                                n /= i
                        }
                        score++
                }
        }
        if n > 1 {
                score++
        }
        return score
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.145.154 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1743264710.A.C56.html
推 Rushia: 想跟你一樣優秀