LeetCode2542最大子序列的分数-解析

时间:2024-06-01 10:24:35

  这题是给的两个数组,如果是给的组合起来的数据结构就会好理解一点,利用贪心的思维,将影响大的乘法作为先查找的元素,将nums2按从大到小排序(假设nums1和nums2绑定为一个对象,可能比下标排序好理解一点),然后维护一个最小堆去遍历即可。

public long maxScore(int[] nums1, int[] nums2, int k) {
        Integer[] ids = new Integer[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ids[i] = i;
        }
        
        Arrays.sort(ids, (i, j) -> nums2[j] - nums2[i]);

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        long sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums1[ids[i]];
            pq.offer(nums1[ids[i]]);
        }

        long ans = sum * nums2[ids[k - 1]];
        for (int i = k; i < nums1.length; i++) {
            int x = nums1[ids[i]];
            if (x > pq.peek()) {
                sum += x - pq.poll();
                pq.offer(x);
                ans = Math.max(ans, sum * nums2[ids[i]]);
            }
        }
        return ans;
    }

在这里插入图片描述