題目

給你兩個下標從 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} 中刪除若干元素得到的剩余集合，也可以不刪除任何元素。

一、代碼實現（貪心+優先隊列）

import ("container/heap""sort"
)func maxScore(nums1 []int, nums2 []int, k int) int64 {n := len(nums1)pairs := make([][]int, n)for i := 0; i < n; i++ {pairs[i] = []int{nums2[i], nums1[i]}}sort.Slice(pairs, func(i, j int) bool {return pairs[i][0] > pairs[j][0]})h := &minHeap{}heap.Init(h)total := 0maxScore := 0for _, pair := range pairs {num2, num1 := pair[0], pair[1]heap.Push(h, num1)total += num1if h.Len() > k {total -= heap.Pop(h).(int)}if h.Len() == k {current := total * num2if current > maxScore {maxScore = current}}}return int64(maxScore)
}type minHeap []intfunc (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() interface{} {old := *hn := len(old)x := old[n-1]*h = old[:n-1]return x
}

二、算法分析

1. 核心思路

• 排序策略：將元素按nums2的值降序排列，確保每次處理當前可能的子序列最小值。
• 貪心選擇：維護一個最小堆，動態保留當前最大的k個nums1值。
• 實時計算：當堆滿k個元素時，立即計算當前可能的最大分數。

2. 關鍵步驟

1. 數據預處理：

   • 將nums1和nums2的元素配對并按nums2降序排列。

2. 堆維護過程：

   • 使用最小堆動態維護最大的k個nums1值。
   • 每當堆元素超過k時，彈出最小值以保持堆大小。

3. 分數計算：

   • 每次堆滿k個元素時，計算當前和與當前nums2最小值的乘積，更新最大分數。

3. 復雜度

指標	值	說明
時間復雜度	O(n log n)	排序主導時間復雜度
空間復雜度	O(n)	存儲排序后的元素對

三、圖解示例

四、邊界條件與擴展

1. 特殊場景驗證

• 全相同元素：當所有nums2值相同時，正確選取最大的k個nums1值。
• k等于數組長度：此時必須全選，分數為總和乘以最小值。
• 大數值測試：驗證算法在極大數值時的正確性。

2. 擴展應用

• 動態k值調整：支持k值根據條件變化時快速重新計算。
• 多維約束：增加其他維度的限制條件進行篩選。
• 分布式計算：處理超大規模數據時分布式排序和堆維護。

3. 多語言實現

import java.util.*;public class Solution {public int maxScore(int[] nums1, int[] nums2, int k) {int n = nums1.length;int[][] pairs = new int[n][2];for (int i = 0; i < n; i++) {pairs[i][0] = nums2[i];pairs[i][1] = nums1[i];}Arrays.sort(pairs, (a, b) -> b[0] - a[0]);PriorityQueue<Integer> heap = new PriorityQueue<>();long total = 0;long maxScore = 0;for (int[] pair : pairs) {int num2 = pair[0];int num1 = pair[1];heap.offer(num1);total += num1;if (heap.size() > k) {total -= heap.poll();}if (heap.size() == k) {maxScore = Math.max(maxScore, total * num2);}}return (int) maxScore;}
}

import heapqdef maxScore(nums1, nums2, k):# 將nums2和nums1的元素配對，并按nums2的值降序排列pairs = sorted(zip(nums2, nums1), key=lambda x: -x[0])heap = []total = 0max_score = 0for num2, num1 in pairs:# 將當前nums1的值加入堆heapq.heappush(heap, num1)total += num1# 如果堆的大小超過k，彈出最小的元素if len(heap) > k:removed = heapq.heappop(heap)total -= removed# 當堆中恰好有k個元素時，計算當前分數if len(heap) == k:current_score = total * num2if current_score > max_score:max_score = current_scorereturn max_score

五、總結與優化

1. 算法對比

方法	優勢	適用場景
貪心+優先隊列	時間效率高	需要動態維護最大值
暴力枚舉	實現簡單	小規模數據
動態規劃	可處理復雜約束	需要狀態轉移的情況

2. 工程優化

• 內存優化：在原數組上操作減少內存消耗。
• 并行排序：使用多線程加速大規模數據排序。
• 剪枝策略：提前終止不可能產生更優解的分支。

3. 擴展方向

• 在線處理：支持數據流動態添加元素。
• 多目標優化：同時考慮多個目標函數的最優解。
• 近似算法：針對超大數據設計近似解法。