---

前言

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

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

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

視頻平臺(tái)：b站-Coder長(zhǎng)路

---

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

來源：《LeetCode 75》

題目及類型

題目鏈接：2542. 最大子序列的分?jǐn)?shù)

類型：數(shù)據(jù)結(jié)構(gòu)/樹/小頂堆

---

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

思路：排序+小頂堆

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

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

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

資料獲取

大家點(diǎn)贊、收藏、關(guān)注、評(píng)論啦~

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

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

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

---

整理者：長(zhǎng)路 整理時(shí)間：2024.1.17