前言
博主介紹：?目前全網(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)
思路：排序+小頂堆
- 對(duì)nums2進(jìn)行降序排序（排序數(shù)組中的值為nums2的索引位置值）【目的：快速定位k個(gè)元素中最小的值，我們是直接由min中的最大值來開始推導(dǎo)】。
- 從排序數(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è)小頂堆里。
- 每次得到一個(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è)值組成的sum
long 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ā)資源及更多資源博客獲取??文章來源：http://www.zghlxwxcb.cn/news/detail-800637.html
整理者：長(zhǎng)路 整理時(shí)間：2024.1.17文章來源地址http://www.zghlxwxcb.cn/news/detail-800637.html
到了這里，關(guān)于LeetCode、2542. 最大子序列的分?jǐn)?shù)【中等，排序+小頂堆】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
