給定兩個長度為
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
TIP
核心思路：依 nums2 降序排序，遍歷時用 Min Heap 維護 nums1 中最大的 k 個值，當前 nums2 值即為最小值。
- 分數 = sum(選中的 nums1) * min(選中的 nums2)
- 如果固定 min(nums2) 的值，則希望 sum(nums1) 最大化
- 將配對依 nums2 降序排序，遍歷時每個 nums2[i] 都可能是最小值
- 用 Min Heap 維護已遍歷元素中 nums1 最大的 k 個，計算當前分數
Approaches
1. Brute Force: Fix Min nums2, Top-k nums1 in Prefix — O(n² log n) / O(n)
- Idea: 依 nums2 降序，對每個 i 當「最小 nums2」，在前綴中取 nums1 最大的 k 個求和 × nums2[i]
- Time:
O(n² log n) - Space:
O(n)
class Solution {
fun maxScore(nums1: IntArray, nums2: IntArray, k: Int): Long {
val n = nums1.size
val order = (0 until n).sortedByDescending { nums2[it] }
var ans = 0L
for (i in order.indices) {
if (i + 1 < k) continue // 前綴不足 k 個
val vals = ArrayList<Int>()
for (j in 0..i) vals.add(nums1[order[j]])
vals.sortDescending()
var sum = 0L
for (t in 0 until k) sum += vals[t]
ans = maxOf(ans, sum * nums2[order[i]].toLong())
}
return ans
}
}⭐ 2. Sorting + Min Heap — O(n log n) / O(n)
- Idea: 依 nums2 降序排序後，用大小為 k 的 Min Heap 維護 nums1 的最大 k 元素總和，每次以當前 nums2 為最小值計算分數
- Time:
O(n log n)- 排序 + heap 操作 - Space:
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 維護最大總和
- Key trick: 依 nums2 降序遍歷確保當前值為最小值，Min Heap 大小固定為 k 確保只保留最大的 k 個 nums1 值。此 pattern 也適用於 1383. Maximum Performance of a Team