操作使得分最大

标签: 栈 贪心 数组 数学 数论 单调栈

难度: Hard

给你一个长度为 n 的正整数数组 nums 和一个整数 k 。

一开始，你的分数为 1 。你可以进行以下操作至多 k 次，目标是使你的分数最大：

  • 选择一个之前没有选过的 非空 子数组 nums[l, ..., r] 。
  • 从 nums[l, ..., r] 里面选择一个 质数分数 最高的元素 x 。如果多个元素质数分数相同且最高，选择下标最小的一个。
  • 将你的分数乘以 x 。

nums[l, ..., r] 表示 nums 中起始下标为 l ，结束下标为 r 的子数组，两个端点都包含。

一个整数的 质数分数 等于 x 不同质因子的数目。比方说， 300 的质数分数为 3 ，因为 300 = 2 * 2 * 3 * 5 * 5 。

请你返回进行至多 k 次操作后，可以得到的 最大分数 。

由于答案可能很大，请你将结果对 109 + 7 取余后返回。

示例 1：

输入：nums = [8,3,9,3,8], k = 2
输出：81
解释：进行以下操作可以得到分数 81 ：
- 选择子数组 nums[2, ..., 2] 。nums[2] 是子数组中唯一的元素。所以我们将分数乘以 nums[2] ，分数变为 1 * 9 = 9 。
- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 1 ，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为 9 * 9 = 81 。
81 是可以得到的最高得分。

示例 2：

输入：nums = [19,12,14,6,10,18], k = 3
输出：4788
解释：进行以下操作可以得到分数 4788 ：
- 选择子数组 nums[0, ..., 0] 。nums[0] 是子数组中唯一的元素。所以我们将分数乘以 nums[0] ，分数变为 1 * 19 = 19 。
- 选择子数组 nums[5, ..., 5] 。nums[5] 是子数组中唯一的元素。所以我们将分数乘以 nums[5] ，分数变为 19 * 18 = 342 。
- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 2，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为  342 * 14 = 4788 。
4788 是可以得到的最高的分。

提示：

  • 1 <= nums.length == n <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= min(n * (n + 1) / 2, 109)

Submission

运行时间: 392 ms

内存: 43.1 MB


# # 贡献法+单调栈
# https://leetcode.cn/problems/apply-operations-to-maximize-score/solutions/2385936/gong-xian-fa-dan-diao-zhan-pythonjavacgo-23c4/
MOD = 10 ** 9 + 7  # 定义模数
MX = 10 ** 5 + 1  # 定义最大值
omega = [0] * MX  # 初始化omega为全0的数组
for i in range(2, MX):  # 预处理omega
    if omega[i] == 0:  # 如果omega[i]为0，说明i是质数
        for j in range(i, MX, i):
            omega[j] += 1  # i是j的一个质因子，因此omega[j]加1


class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 获取nums的长度
        left = [-1] * n  # 初始化left为全-1的数组，表示质数分数大于等于omega[nums[i]]的左侧最近元素下标
        right = [n] * n  # 初始化right为全n的数组，表示质数分数大于omega[nums[i]]的右侧最近元素下标
        st = []  # 初始化空栈st
        for i, v in enumerate(nums):  # 遍历nums
            while st and omega[nums[st[-1]]] < omega[v]:  # 当st非空且omega[nums[st的最后一个元素]]小于omega[v]时
                right[st.pop()] = i  # 将st的最后一个元素弹出，并将right的对应位置设为i

            if st:
                left[i] = st[-1]  # 如果st非空，更新left[i]为st的最后一个元素
                
            st.append(i)  # 将i添加到st的末尾

        ans = 1  # 初始化ans为1
        for i, v, l, r in sorted(zip(range(n), nums, left, right), key=lambda z: -z[1]):  # 对(i, v, l, r)按v的降序排序
            tot = (i - l) * (r - i)  # 计算总数
            if tot >= k:  # 如果总数大于等于k
                ans = ans * pow(v, k, MOD) % MOD  # 更新ans
                break  # 跳出循环

            ans = ans * pow(v, tot, MOD) % MOD  # 更新ans
            k -= tot  # 更新剩余操作次数

        return ans  # 返回ans

Explain

本题解采用的是质数分数的贡献法结合单调栈的策略。首先，通过预处理计算每个数的质数分数（即不同质因子的数量）。使用单调栈来为每个元素找到左侧和右侧第一个质数分数更低的元素位置。这些位置帮助确定每个元素可以作为最大值的子数组的范围。对数组元素按照值进行降序排序后，尝试最多k次操作，每次选择范围最大的元素以最大化分数。通过计算该元素出现的次数（由其在单调栈中确定的左右边界计算得出），决定是否可以用完所有的操作。如果在某点用完所有操作，或者找到了最优解，循环终止。

时间复杂度: O(n log n)

空间复杂度: O(n)

# 贡献法+单调栈

MOD = 10 ** 9 + 7  # 定义模数
MX = 10 ** 5 + 1  # 最大数值范围
omega = [0] * MX  # 质数分数数组初始化
for i in range(2, MX):  # 筛法计算每个数的质数分数
    if omega[i] == 0:  # 如果是质数
        for j in range(i, MX, i):
            omega[j] += 1  # 增加质因子计数

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        left = [-1] * n  # 左边界初始化
        right = [n] * n  # 右边界初始化
        st = []  # 单调栈初始化
        for i, v in enumerate(nums):  # 构建单调栈及左右边界
            while st and omega[nums[st[-1]]] < omega[v]:
                right[st.pop()] = i
            if st:
                left[i] = st[-1]
            st.append(i)
        ans = 1  # 初始分数
        for i, v, l, r in sorted(zip(range(n), nums, left, right), key=lambda z: -z[1]):  # 按值降序遍历
            tot = (i - l) * (r - i)  # 计算可操作次数
            if tot >= k:  # 如果足够完成剩余操作
                ans = ans * pow(v, k, MOD) % MOD  # 更新分数
                break
            ans = ans * pow(v, tot, MOD) % MOD  # 否则继续累乘
            k -= tot  # 减少剩余操作次数
        return ans  # 返回结果

Explore

质数分数是指某个整数的不同质因子的数量。例如，12的质因子有2和3，因此它的质数分数是2。为了有效地计算每个整数的质数分数，我们采用筛法（例如埃拉托斯特尼筛法）。通过这种方法，我们从最小的质数开始，标记它的所有倍数，并增加其质因子的计数。这种方式使得我们能够高效地处理大范围内的整数，并对每个数的质因子进行计算，避免了对每个数进行独立因式分解的重复和计算上的不便。

在本题中，单调栈用于为每个数组元素找到左侧和右侧第一个质数分数更低的元素。这样可以确定每个元素可以作为最大值的子数组的范围。选择单调栈是因为它能够在一次遍历中解决这类“下一个更小元素”或“前一个更小元素”的问题，同时保持时间复杂度为O(n)。如果使用其他数据结构如堆或二分搜索树，则处理这类问题通常会更复杂且效率较低。

每个元素的子数组范围是通过单调栈计算的左右边界确定的。在构建单调栈的过程中，为每个元素找到左侧和右侧第一个质数分数更低的元素。这些位置即为子数组的边界。左边界是当前元素左侧第一个质数分数更低的元素的位置，右边界是右侧第一个质数分数更低的元素的位置。因此，每个元素的子数组范围可以通过这些边界确定。

按元素值降序排序的目的是优先处理值较大的元素。因为我们的目标是最大化分数，所以首先考虑值较大的元素可能会带来更高的分数贡献。这样的排序保证我们在尽可能使用较少的操作次数的情况下，最大化每次操作的贡献，从而在给定操作次数内达到最大的分数。排序后，算法首先尝试将操作次数分配给值最大的元素，这通常可以使得总分数更优。