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
}

想跟你一样优秀