Leetcode 2818. Apply Operations to Maximize Score

[Woodyiiiiiii]

2818. Apply Operations to Maximize Score

2818. Apply Operations to Maximize Score

单调栈题单：
496. Next Greater Element I
503. Next Greater Element II
556. Next Greater Element III
2454. Next Greater Element IV (未AC)
2104. Sum of Subarray Ranges

贡献法题单：
907. Sum of Subarray Minimums
1856. Maximum Subarray Min-Product
2281. Sum of Total Strength of Wizards (未AC)

我一开始以为是用堆先记录所有长度为1的子数组，然后依次取最大，然后扩展，就像之前做过的那样。但发现k特别大，所以要对k进行处理，要结合数组长度n有效忽略k。所以这个方法不可行了。

后来发现可以用贡献法，先求每个元素能够成为最大不同质因数个数的子数组个数，然后从最大元素开始，依次往下计算，这样就能从n出发，模糊了k的大小。这也是从时间复杂度破题。

那么卡点在于如何在O(n)范围内求每个元素辐射的范围。一开始我还想着用TreeMap来做，受了第三题的影响，但很明显有问题。思考下，我们求的是每个元素不同质因数大小最大范围，假设从左往右遍历，对于每个元素，要求的是最左边能到达的不同质因数大小大于等于该元素的位置，到底用什么结构呢？单调栈。我对这个知识点不熟悉，有些遗忘了。

单调栈只能有一个方向，所以我需要遍历两遍数组，求的左右范围，其中范围计算是leftLen += (leftLen * rightLen) 包括自己本身。

然后结合堆，从最大元素开始计算，然后用BigInteger(不是BigDecimal)快速幂，取模计算。

综合题目，很有学习价值。涉及知识点：

1. 贡献法
2. 单调栈
3. 求质因数
4. 快速幂

import java.math.BigInteger;

class Solution {
    public int maximumScore(List<Integer> nums, int k) {
        int n = nums.size();
        int[] counts = new int[n];
        for (int i = 0; i < n; i++) {
            counts[i] = cntOfDistinctPF(nums.get(i));
        }
        final int MOD = (int) 1e9 + 7;
        BigInteger ans = BigInteger.ONE;

        // init - left to right
        long[] sums = new long[n];
        LinkedList<Integer> stack = new LinkedList<>();     // 最小栈
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && counts[i] > counts[stack.peek()]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                sums[i] = i + 1;
            } else {
                sums[i] = i - stack.peek();
            }
            stack.push(i);
        }
        // right to left
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && counts[i] >= counts[stack.peek()]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                sums[i] += (sums[i] * (n - i - 1));
            } else {
                sums[i] += (sums[i] * (stack.peek() - i - 1));
            }
            stack.push(i);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);
        for (int i = 0; i < n; i++) {
            pq.add(new int[]{nums.get(i), i});
        }

        while (k > 0 && !pq.isEmpty()) {
            int[] poll = pq.poll();
            long cnt = Math.min(k, sums[poll[1]]);
            BigInteger cur = BigInteger.valueOf(poll[0]).modPow(BigInteger.valueOf(cnt), BigInteger.valueOf(MOD));
//            BigInteger cur = BigInteger.valueOf(poll[0]).pow((int) cnt);
            ans = ans.multiply(cur).mod(BigInteger.valueOf(MOD));
            k -= (int) cnt;
        }

        return ans.intValue();
    }

    private int cntOfDistinctPF(int num) {
        int cnt = 0;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                cnt++;
//                System.out.print(i + " ");
                while (num % i == 0) {
                    num /= i;
                }
            }
        }
        if (num > 1) {
//            System.out.print(num + " ");
            cnt++;
        }
//        System.out.println();
        return cnt;
    }
}