Maximum Subsequence Score

題目描述

給定兩個長度為 n 的整數陣列 nums1 和 nums2，以及一個正整數 k。從索引中選出 k 個不同的索引 i1, i2, ..., ik，分數定義為 (nums1[i1] + nums1[i2] + ... + nums1[ik]) * min(nums2[i1], nums2[i2], ..., nums2[ik])。回傳最大可能分數。

輸入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
輸出：12
解釋：選索引 0, 2, 3 → (1+3+2) * min(2,3,4) = 6*2 = 12

解題思路

配對排序

將 (nums2[i], nums1[i]) 配對，按 nums2 降序排列。例如 nums1=[1,3,3,2], nums2=[2,1,3,4] → 排序後配對為 (4,2),(3,3),(2,1),(1,3)

遍歷配對

依序遍歷排序後的配對，因為 nums2 遞減，當前的 nums2 值一定是已遍歷中最小的，直接作為 min 使用

維護 Min Heap

用大小為 K 的 Min Heap 追蹤最大的 K 個 nums1 值。堆頂是最小值，方便判斷是否該替換

堆滿時計算

堆中元素達 K 個時，計算 sum × 當前 nums2 並與目前最佳答案比較，取較大值

替換最小值

堆已滿時加入新元素會讓堆大小超過 K，彈出堆頂（最小的 nums1）以維持 K 個最大值

程式碼

C#

csharp

public class Solution {
    public long MaxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.Length;
        // 按 nums2 降序排列
        var indices = Enumerable.Range(0, n)
            .OrderByDescending(i => nums2[i]).ToArray();
        
        var minHeap = new PriorityQueue<int, int>();
        long sum = 0, result = 0;
        
        foreach (int i in indices) {
            sum += nums1[i];
            minHeap.Enqueue(nums1[i], nums1[i]);
            
            // 堆超過 k 個，移除最小的
            if (minHeap.Count > k) {
                sum -= minHeap.Dequeue();
            }
            
            // 剛好 k 個時計算分數
            if (minHeap.Count == k) {
                result = Math.Max(result, sum * nums2[i]);
            }
        }
        return result;
    }
}

TypeScript

typescript

function maxScore(nums1: number[], nums2: number[], k: number): number {
    const n = nums1.length;
    // 按 nums2 降序排列索引
    const indices = Array.from({length: n}, (_, i) => i)
        .sort((a, b) => nums2[b] - nums2[a]);
    
    // 簡易 Min Heap（用排序陣列模擬）
    const heap: number[] = [];
    let sum = 0, result = 0;
    
    for (const i of indices) {
        sum += nums1[i];
        // 插入並維護排序
        heap.push(nums1[i]);
        heap.sort((a, b) => a - b);
        
        if (heap.length > k) {
            sum -= heap.shift()!; // 移除最小
        }
        if (heap.length === k) {
            result = Math.max(result, sum * nums2[i]);
        }
    }
    return result;
}

Python

python

import heapq
 
def maxScore(nums1: list[int], nums2: list[int], k: int) -> int:
    # 按 nums2 降序排列配對
    pairs = sorted(zip(nums2, nums1), reverse=True)
    
    heap = []  # min heap 維護最大的 k 個 nums1
    total = 0
    result = 0
    
    for n2, n1 in pairs:
        total += n1
        heapq.heappush(heap, n1)
        
        if len(heap) > k:
            total -= heapq.heappop(heap)  # 移除最小
        
        if len(heap) == k:
            result = max(result, total * n2)  # n2 是當前最小的 nums2
    
    return result

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n log n) | O(n) |

Time：排序 O(n log n) + 遍歷 n 個配對各做一次 heap push/pop O(log k)，合計 O(n log n)
Space：排序用的索引陣列 O(n)，heap 最多 K 個元素 O(k)，整體 O(n)

圖解

按 nums2 降序排序

排序後→

依序遍歷每個配對

加入 nums1→

Min Heap (size K)

堆滿 K 個→

sum × min(nums2) = score

更新答案→

取最大 score

圖表展示了核心流程：先按 nums2 降序排列保證遍歷時 nums2 值遞減，再用 Min Heap 動態維護最大的 K 個 nums1 值。每次堆滿 K 個時，當前 nums2 就是所選元素中的最小值，直接計算分數並更新答案。

進階觀點

💡面試追問

如果 K 不固定，要求所有可能 K 值的最大分數怎麼辦？ 在遍歷過程中，每當 heap 大小增加到新的 K 值時就記錄一次 sum × 當前 nums2，最後取所有 K 值對應答案的最大值。時間複雜度不變，仍為 O(n log n)。
這題和 1383. Maximum Performance of a Team 的關係？ 兩題框架幾乎相同：排序 + Min Heap。1383 取 sum + min 而非 sum × min，但貪心邏輯一致——按「min 來源」降序遍歷，用 heap 維護最佳的前 K 個值。
為什麼按 nums2 降序排列？ 降序遍歷保證當前 nums2 值一定 ≤ 所有已遍歷的 nums2 值，所以它自動就是被選中元素的 min(nums2)，不需要額外的資料結構追蹤最小值。

邊界情況

k 等於 n：必須選所有元素，Min Heap 不會做任何彈出操作，答案就是 sum(nums1) × min(nums2)
所有 nums2 值相同：min 值固定，問題退化為選最大的 K 個 nums1 值求和，直接排序 nums1 取前 K 大即可
nums1 中有 0：不影響正確性，但 0 會被 heap 彈出（因為它是最小的），不會留在最終的 K 個中（除非其他值也是 0）

理解測驗

🤔 為什麼要按 nums2 降序排列後遍歷？

🤔 Min Heap 在這題中的作用是什麼？