Description
給定兩個長度為
n的整數陣列nums1和nums2，以及正整數k。從索引0到n-1中選出長度為k的子序列，分數為nums1中對應元素的總和乘以nums2中對應元素的最小值。回傳最大可能分數。
Example:
Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3 Output: 12
Intuition#
核心思路：依 nums2 降序排序，遍歷時用 Min Heap 維護 nums1 中最大的 k 個值，當前 nums2 值即為最小值。
- 分數 = sum(選中的 nums1) * min(選中的 nums2)
- 如果固定 min(nums2) 的值，則希望 sum(nums1) 最大化
- 將配對依 nums2 降序排序，遍歷時每個 nums2[i] 都可能是最小值
- 用 Min Heap 維護已遍歷元素中 nums1 最大的 k 個，計算當前分數
Approaches#
⭐1: Sorting + Min Heap#
- 概念: 依 nums2 降序排序後，用大小為 k 的 Min Heap 維護 nums1 的最大 k 元素總和，每次以當前 nums2 為最小值計算分數
- 時間複雜度:
O(n log n)- 排序 + heap 操作 - 空間複雜度:
O(n)
class Solution {
fun maxScore(nums1: IntArray, nums2: IntArray, k: Int): Long {
val n = nums1.size
val indices = (0 until n).sortedByDescending { nums2[it] }
val minHeap = PriorityQueue<Int>()
var sum = 0L
var result = 0L
for (idx in indices) {
minHeap.offer(nums1[idx])
sum += nums1[idx]
if (minHeap.size > k) {
sum -= minHeap.poll()
}
if (minHeap.size == k) {
result = maxOf(result, sum * nums2[idx])
}
}
return result
}
}🔑 Takeaways#
- Pattern: 「乘積 = 總和 * 最小值」問題 → 排序固定最小值，Heap 維護最大總和
- 關鍵技巧: 依 nums2 降序遍歷確保當前值為最小值，Min Heap 大小固定為 k 確保只保留最大的 k 個 nums1 值。此 pattern 也適用於 1383. Maximum Performance of a Team