LeetCode 2542. 最大子序列的分数（排序+小顶堆）

文章目录

• LeetCode、2542. 最大子序列的分数【中等，排序+小顶堆】
• 题目及类型
• 思路及代码实现

---

LeetCode、2542. 最大子序列的分数【中等，排序+小顶堆】

来源：《LeetCode 75》

题目及类型

题目链接：2542. 最大子序列的分数

类型：数据结构/树/小顶堆

---

思路及代码实现

思路：排序+小顶堆

1. 对nums2进行降序排序（排序数组中的值为nums2的索引位置值）【目的：快速定位k个元素中最小的值，我们是直接由min中的最大值来开始推导】。
2. 从排序数组的第一个元素开始，由于是顺序，每次取到的i位置，其nums2[i]都是在[i-k+1,i]中最小的，那么就可以实际就是题目中的min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1])。那么对于进行k个元素的和怎么计算呢？每次取到索引值，我们就直接累加这个nums1[i]到sum中，并且将这个值添加到一个小顶堆里。
3. 每次得到一个新的i位置时，sum会累加nums1[i]，同时将nums2[i]作为min(k个nums2元素)的最小值，最后计算得到结果后，再将小顶堆中的最小值移除（问这个移除是否影响到min最小值的确定，并不会原因是每次取到的nums2[i]都已经是前面范围的最小值了！所以我们也无需管移除的最小值是什么）

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        //维护k个元素的小顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);
        //创建nums2数组的索引数组，并且根据nums2数组中的值降序排列的索引数组
        Integer[] sorteds = new Integer[n];
        for (int i = 0; i < n; i ++) {
            sorteds[i] = i;
        }
        //根据nums2的值进行降序排列
        Arrays.sort(sorteds, (i, j)->nums2[j]-nums2[i]);
		//定义一个k个值组成的sum
        long sum = 0L;
        //首先合并k-1个元素值
        for (int i = 0; i < k - 1; i ++) {
            sum += nums1[sorteds[i]];//合并的是基于索引值的nums1数组元素
            queue.offer(nums1[sorteds[i]]);
        }
        long ans = 0L;
        //遍历剩余的所有元素，每次构成一个新的组合
        for (int i = k - 1; i < n; i ++) {
            //将当前值累加，并将当前值添加到
            sum += nums1[sorteds[i]];
            queue.offer(nums1[sorteds[i]]);
            //sum即为k个元素之和   nums2[sorteds[i]]则为k个中最小的值
            ans = Math.max(ans, sum * nums2[sorteds[i]]);
            //出小顶堆中最小的元素
            sum -= queue.poll();
        }
        return ans;
    }
}

---

整理者：长路 整理时间：2024.1.17