---

前言

博主介紹：?目前全網(wǎng)粉絲2W+，csdn博客專家、Java領域優(yōu)質(zhì)創(chuàng)作者，博客之星、阿里云平臺優(yōu)質(zhì)作者、專注于Java后端技術領域。

涵蓋技術內(nèi)容：Java后端、算法、分布式微服務、中間件、前端、運維、ROS等。

博主所有博客文件目錄索引：博客目錄索引(持續(xù)更新)

視頻平臺：b站-Coder長路

---

LeetCode、2542. 最大子序列的分數(shù)【中等，排序+小頂堆】

來源：《LeetCode 75》

題目及類型

題目鏈接：2542. 最大子序列的分數(shù)

類型：數(shù)據(jù)結構/樹/小頂堆

---

思路及代碼實現(xiàn)

思路：排序+小頂堆

1. 對nums2進行降序排序（排序數(shù)組中的值為nums2的索引位置值）【目的：快速定位k個元素中最小的值，我們是直接由min中的最大值來開始推導】。
2. 從排序數(shù)組的第一個元素開始，由于是順序，每次取到的i位置，其nums2[i]都是在[i-k+1,i]中最小的，那么就可以實際就是題目中的min(nums2[i0] , nums2[i1], … ,nums2[ik - 1])。那么對于進行k個元素的和怎么計算呢？每次取到索引值，我們就直接累加這個nums1[i]到sum中，并且將這個值添加到一個小頂堆里。
3. 每次得到一個新的i位置時，sum會累加nums1[i]，同時將nums2[i]作為min(k個nums2元素)的最小值，最后計算得到結果后，再將小頂堆中的最小值移除（問這個移除是否影響到min最小值的確定，并不會原因是每次取到的nums2[i]都已經(jīng)是前面范圍的最小值了！所以我們也無需管移除的最小值是什么）

復雜度分析：時間復雜度O(n.logn)；空間復雜度O(n)

class Solution {public long maxScore(int[] nums1, int[] nums2, int k) {int n = nums1.length;//維護k個元素的小頂堆PriorityQueue<Integer> queue = new PriorityQueue<>(k);//創(chuàng)建nums2數(shù)組的索引數(shù)組，并且根據(jù)nums2數(shù)組中的值降序排列的索引數(shù)組Integer[] sorteds = new Integer[n];for (int i = 0; i < n; i ++) {sorteds[i] = i;}//根據(jù)nums2的值進行降序排列Arrays.sort(sorteds, (i, j)->nums2[j]-nums2[i]);//定義一個k個值組成的sumlong sum = 0L;//首先合并k-1個元素值for (int i = 0; i < k - 1; i ++) {sum += nums1[sorteds[i]];//合并的是基于索引值的nums1數(shù)組元素queue.offer(nums1[sorteds[i]]);}long ans = 0L;//遍歷剩余的所有元素，每次構成一個新的組合for (int i = k - 1; i < n; i ++) {//將當前值累加，并將當前值添加到sum += nums1[sorteds[i]];queue.offer(nums1[sorteds[i]]);//sum即為k個元素之和   nums2[sorteds[i]]則為k個中最小的值ans = Math.max(ans, sum * nums2[sorteds[i]]);//出小頂堆中最小的元素sum -= queue.poll();}return ans;}
}

資料獲取

大家點贊、收藏、關注、評論啦~

精彩專欄推薦訂閱：在下方專欄👇🏻

• 長路-文章目錄匯總（算法、后端Java、前端、運維技術導航）：博主所有博客導航索引匯總
• 開源項目Studio-Vue—校園工作室管理系統(tǒng)(含前后臺，SpringBoot+Vue)：博主個人獨立項目，包含詳細部署上線視頻，已開源
• 學習與生活-專欄：可以了解博主的學習歷程
• 算法專欄：算法收錄

更多博客與資料可查看👇🏻獲取聯(lián)系方式👇🏻，🍅文末獲取開發(fā)資源及更多資源博客獲取🍅

---

整理者：長路 整理時間：2024.1.17