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
}

想跟你一樣優秀