LeetCode 题解工作台
操作使得分最大
给你一个长度为 n 的正整数数组 nums 和一个整数 k 。 一开始，你的分数为 1 。你可以进行以下操作至多 k 次，目标是使你的分数最大： 选择一个之前没有选过的 非空 子数组 nums[l, ..., r] 。 从 nums[l, ..., r] 里面选择一个 质数分数 最高的元素 x 。如…
7
题型
5
代码语言
3
相关题
当前训练重点
困难 · 栈·状态
答案摘要
我们不妨考虑枚举每个元素 作为质数分数最高的元素，那么我们需要找出左边第一个质数分数大于等于当前元素的位置 ，以及右边第一个质数分数大于当前元素的位置 ，那么以当前元素为最高质数分数的子数组有 $cnt = (i - l) \times (r - i)$ 个，它对答案的贡献为 。 而题目限制了最多进行 次操作，我们可以贪心地从大到小枚举 ，每一次算出其子数组的个数 ，如果 $cnt \le k…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个长度为 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 <= 1051 <= nums[i] <= 1051 <= k <= min(n * (n + 1) / 2, 109)
解题思路
方法一：单调栈 + 排序贪心
我们不妨考虑枚举每个元素 作为质数分数最高的元素，那么我们需要找出左边第一个质数分数大于等于当前元素的位置 ，以及右边第一个质数分数大于当前元素的位置 ，那么以当前元素为最高质数分数的子数组有 个，它对答案的贡献为 。
而题目限制了最多进行 次操作，我们可以贪心地从大到小枚举 ，每一次算出其子数组的个数 ，如果 ，那么 对答案的贡献就是 ，然后我们更新 ，继续枚举下一个元素。如果 ，那么 对答案的贡献就是 ，然后退出循环。
枚举结束，返回答案即可。注意，由于幂次较大，我们需要用到快速幂。
时间复杂度 ，空间复杂度 。其中 是数组的长度。
def primeFactors(n):
i = 2
ans = set()
while i * i <= n:
while n % i == 0:
ans.add(i)
n //= i
i += 1
if n > 1:
ans.add(n)
return len(ans)
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
mod = 10**9 + 7
arr = [(i, primeFactors(x), x) for i, x in enumerate(nums)]
n = len(nums)
left = [-1] * n
right = [n] * n
stk = []
for i, f, x in arr:
while stk and stk[-1][0] < f:
stk.pop()
if stk:
left[i] = stk[-1][1]
stk.append((f, i))
stk = []
for i, f, x in arr[::-1]:
while stk and stk[-1][0] <= f:
stk.pop()
if stk:
right[i] = stk[-1][1]
stk.append((f, i))
arr.sort(key=lambda x: -x[2])
ans = 1
for i, f, x in arr:
l, r = left[i], right[i]
cnt = (i - l) * (r - i)
if cnt <= k:
ans = ans * pow(x, cnt, mod) % mod
k -= cnt
else:
ans = ans * pow(x, k, mod) % mod
break
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O\left(n \times \left(\log{n} + \frac{\sqrt{m}}{\log{m}} + \log{k}\right) + m \log{\log{m}}\right) |
| 空间 | O(m + n) |
面试官常问的追问
外企场景- question_mark
Evaluates understanding of efficient prime factorization and number theory.
- question_mark
Assesses ability to use stack-based data structures for state management.
- question_mark
Tests knowledge of greedy algorithms and subarray optimization techniques.
常见陷阱
外企场景- error
Overlooking the importance of optimizing prime factorization time, which can lead to inefficient solutions.
- error
Incorrect subarray selection, which can result in suboptimal scores.
- error
Failing to effectively manage the stack, leading to incorrect subarray evaluations.
进阶变体
外企场景- arrow_right_alt
Change the scoring operation to sum instead of multiply.
- arrow_right_alt
Consider allowing a different number of operations, increasing complexity.
- arrow_right_alt
Increase the size of the array or range of k to test scalability of the solution.