題目描述

??給你兩個下標從 0 開始的整數數組 nums1 和 nums2 ，兩者長度都是 n ，再給你一個正整數 k 。你必須從 nums1 中選一個長度為 k 的 子序列 對應的下標。

對于選擇的下標 i0 ，i1 ，…， ik - 1 ，你的 分數 定義如下：nums1 中下標對應元素求和，乘以 nums2 中下標對應元素的 最小值 。用公式表示： (nums1[i0] + nums1[i1] +…+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], … ,nums2[ik - 1]) 。請你返回 最大 可能的分數。一個數組的 子序列 下標是集合 {0, 1, …, n-1} 中刪除若干元素得到的剩余集合，也可以不刪除任何元素。

解析

??這題是給的兩個數組，如果是給的組合起來的數據結構就會好理解一點，利用貪心的思維，將影響大的乘法作為先查找的元素，將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;}