2818. 应用操作最大化分数

Hard

题目描述

给你一个由 n 个正整数组成的数组 nums 和一个整数 k。

最初，你的分数是 1。你必须通过最多应用 k 次以下操作来最大化你的分数：

选择任何一个你之前没有选择过的非空子数组 nums[l, …, r]。
从 nums[l, …, r] 中选择具有最高质数分数的元素 x。如果存在多个这样的元素，选择索引最小的元素。
将你的分数乘以 x。

这里，nums[l, …, r] 表示 nums 从索引 l 开始到索引 r 结束的子数组（两端都包含）。

整数 x 的质数分数等于 x 的不同质因数的个数。例如，300 的质数分数是 3，因为 300 = 2 * 2 * 3 * 5 * 5。

返回应用最多 k 次操作后可能获得的最大分数。

由于答案可能很大，返回它对 10^9 + 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 <= 10^5
1 <= nums[i] <= 10^5
1 <= k <= min(n * (n + 1) / 2, 10^9)

解题思路

这道题的核心思路是贪心算法配合单调栈：

计算质数分数：对每个数字计算其不同质因数的个数，这是选择的优先级依据。
寻找贡献范围：对每个位置 i，需要找到它能成为最大质数分数的所有子数组范围。使用单调栈分别找到：
- left[i]：左边第一个质数分数 >= nums[i] 的位置
- right[i]：右边第一个质数分数 > nums[i] 的位置
这样位置 i 能贡献的子数组数量为 (i - left[i]) * (right[i] - i)。
贪心选择：按质数分数从大到小排序，然后按数值从大到小选择。每个元素最多被选择其贡献次数，直到用完 k 次操作。
快速幂优化：使用快速幂计算大数的幂运算，避免超时。

关键点是理解每个元素在多少个子数组中会被选中，然后贪心地优先选择质数分数高、数值大的元素。

代码实现

class Solution {
public:
    const int MOD = 1e9 + 7;
    
    int countPrimeFactors(int n) {
        int count = 0;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                count++;
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) count++;
        return count;
    }
    
    long long quickPow(long long base, long long exp) {
        long long result = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp & 1) result = (result * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return result;
    }
    
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> primeScore(n);
        
        for (int i = 0; i < n; i++) {
            primeScore[i] = countPrimeFactors(nums[i]);
        }
        
        vector<int> left(n, -1), right(n, n);
        stack<int> stk;
        
        // Find left boundaries
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && primeScore[stk.top()] < primeScore[i]) {
                stk.pop();
            }
            if (!stk.empty()) left[i] = stk.top();
            stk.push(i);
        }
        
        while (!stk.empty()) stk.pop();
        
        // Find right boundaries
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && primeScore[stk.top()] <= primeScore[i]) {
                stk.pop();
            }
            if (!stk.empty()) right[i] = stk.top();
            stk.push(i);
        }
        
        vector<pair<int, int>> candidates;
        for (int i = 0; i < n; i++) {
            long long count = (long long)(i - left[i]) * (right[i] - i);
            candidates.push_back({i, min((long long)k, count)});
        }
        
        sort(candidates.begin(), candidates.end(), [&](const pair<int, int>& a, const pair<int, int>& b) {
            if (primeScore[a.first] != primeScore[b.first]) {
                return primeScore[a.first] > primeScore[b.first];
            }
            return nums[a.first] > nums[b.first];
        });
        
        long long result = 1;
        for (auto& [idx, count] : candidates) {
            if (k <= 0) break;
            int use = min(k, count);
            result = (result * quickPow(nums[idx], use)) % MOD;
            k -= use;
        }
        
        return result;
    }
};

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        
        def count_prime_factors(n):
            count = 0
            i = 2
            while i * i <= n:
                if n % i == 0:
                    count += 1
                    while n % i == 0:
                        n //= i
                i += 1
            if n > 1:
                count += 1
            return count
        
        def quick_pow(base, exp):
            result = 1
            base %= MOD
            while exp > 0:
                if exp & 1:
                    result = (result * base) % MOD
                base = (base * base) % MOD
                exp >>= 1
            return result
        
        n = len(nums)
        prime_score = [count_prime_factors(x) for x in nums]
        
        left = [-1] * n
        right = [n] * n
        stack = []
        
        # Find left boundaries
        for i in range(n):
            while stack and prime_score[stack[-1]] < prime_score[i]:
                stack.pop()
            if stack:
                left[i] = stack[-1]
            stack.append(i)
        
        stack.clear()
        
        # Find right boundaries
        for i in range(n - 1, -1, -1):
            while stack and prime_score[stack[-1]] <= prime_score[i]:
                stack.pop()
            if stack:
                right[i] = stack[-1]
            stack.append(i)
        
        candidates = []
        for i in range(n):
            count = (i - left[i]) * (right[i] - i)
            candidates.append((i, min(k, count)))
        
        candidates.sort(key=lambda x: (-prime_score[x[0]], -nums[x[0]]))
        
        result = 1
        for idx, count in candidates:
            if k <= 0:
                break
            use = min(k, count)
            result = (result * quick_pow(nums[idx], use)) % MOD
            k -= use
        
        return result

public class Solution {
    private const int MOD = 1000000007;
    
    private int CountPrimeFactors(int n) {
        int count = 0;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                count++;
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) count++;
        return count;
    }
    
    private long QuickPow(long baseNum, long exp) {
        long result = 1;
        baseNum %= MOD;
        while (exp > 0) {
            if ((exp & 1) == 1) result = (result * baseNum) % MOD;
            baseNum = (baseNum * baseNum) % MOD;
            exp >>= 1;
        }
        return result;
    }
    
    public int MaximumScore(IList<int> nums, int k) {
        int n = nums.Count;
        int[] primeScore = new int[n];
        
        for (int i = 0; i < n; i++) {
            primeScore[i] = CountPrimeFactors(nums[i]);
        }
        
        int[] left = new int[n];
        int[] right = new int[n];
        Array.Fill(left, -1);
        Array.Fill(right, n);
        
        Stack<int> stack = new Stack<int>();
        
        // Find left boundaries
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && primeScore[stack.Peek()] < primeScore[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) left[i] = stack.Peek();
            stack.Push(i);
        }
        
        stack.Clear();
        
        // Find right boundaries
        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && primeScore[stack.Peek()] <= primeScore[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) right[i] = stack.Peek();
            stack.Push(i);
        }
        
        List<(int idx, long count)> candidates = new List<(int, long)>();
        for (int i = 0; i < n; i++) {
            long count = (long)(i - left[i]) * (right[i] - i);
            candidates.Add((i, Math.Min(k, count)));
        }
        
        candidates.Sort((a, b) => {
            if (primeScore[a.idx] != primeScore[b.idx]) {
                return primeScore[b.idx].CompareTo(primeScore[a.idx]);
            }
            return nums[b.idx].CompareTo(nums[a.idx]);
        });
        
        long result = 1;
        foreach (var (idx, count) in candidates) {
            if (k <= 0) break;
            long use = Math.Min(k, count);
            result = (result * QuickPow(nums[idx], use)) % MOD;
            k -= (int)use;
        }
        
        return (int)result;
    }
}

var maximumScore = function(nums, k) {
    const MOD = 1000000007n;
    const n = nums.length;
    
    // Calculate prime scores
    const primeScore = new Array(100001).fill(0);
    for (let i = 2; i <= 100000; i++) {
        if (primeScore[i] === 0) {
            for (let j = i; j <= 100000; j += i) {
                primeScore[j]++;
            }
        }
    }
    
    const scores = nums.map(x => primeScore[x]);
    
    // Find left and right boundaries for each element
    const left = new Array(n);
    const right = new Array(n);
    const stack = [];
    
    // Find left boundary (previous greater or equal prime score)
    for (let i = 0; i < n; i++) {
        while (stack.length && scores[stack[stack.length - 1]] < scores[i]) {
            stack.pop();
        }
        left[i] = stack.length ? stack[stack.length - 1] + 1 : 0;
        stack.push(i);
    }
    
    stack.length = 0;
    
    // Find right boundary (next greater prime score)
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length && scores[stack[stack.length - 1]] <= scores[i]) {
            stack.pop();
        }
        right[i] = stack.length ? stack[stack.length - 1] - 1 : n - 1;
        stack.push(i);
    }
    
    // Calculate contribution of each element
    const contributions = [];
    for (let i = 0; i < n; i++) {
        const leftCount = BigInt(i - left[i] + 1);
        const rightCount = BigInt(right[i] - i + 1);
        contributions.push({
            value: BigInt(nums[i]),
            count: leftCount * rightCount,
            index: i
        });
    }
    
    // Sort by value descending
    contributions.sort((a, b) => b.value > a.value ? 1 : b.value < a.value ? -1 : 0);
    
    // Power function
    function power(base, exp, mod) {
        let result = 1n;
        base = base % mod;
        while (exp > 0) {
            if (exp % 2n === 1n) {
                result = (result * base) % mod;
            }
            exp = exp / 2n;
            base = (base * base) % mod;
        }
        return result;
    }
    
    let result = 1n;
    let remaining = BigInt(k);
    
    for (const contrib of contributions) {
        if (remaining === 0n) break;
        const use = remaining < contrib.count ? remaining : contrib.count;
        result = (result * power(contrib.value, use, MOD)) % MOD;
        remaining -= use;
    }
    
    return Number(result);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目