当前位置: 首页 > news >正文

LeetCode算法题(Go语言实现)_51

题目

给你两个下标从 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的值降序排列,确保每次处理当前可能的子序列最小值。
  • 贪心选择:维护一个最小堆,动态保留当前最大的knums1值。
  • 实时计算:当堆满k个元素时,立即计算当前可能的最大分数。
2. 关键步骤
  1. 数据预处理

    • nums1nums2的元素配对并按nums2降序排列。
  2. 堆维护过程

    • 使用最小堆动态维护最大的knums1值。
    • 每当堆元素超过k时,弹出最小值以保持堆大小。
  3. 分数计算

    • 每次堆满k个元素时,计算当前和与当前nums2最小值的乘积,更新最大分数。
3. 复杂度
指标说明
时间复杂度O(n log n)排序主导时间复杂度
空间复杂度O(n)存储排序后的元素对

三、图解示例

在这里插入图片描述

四、边界条件与扩展

1. 特殊场景验证
  • 全相同元素:当所有nums2值相同时,正确选取最大的knums1值。
  • 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. 扩展方向
  • 在线处理:支持数据流动态添加元素。
  • 多目标优化:同时考虑多个目标函数的最优解。
  • 近似算法:针对超大数据设计近似解法。
http://www.xdnf.cn/news/5131.html

相关文章:

  • Vue3如何选择传参方式
  • C++面试
  • 【HDFS入门】HDFS核心配置与优化指南概述
  • 【Python学习笔记】Pandas实现Excel质检记录表初审、复核及质检统计
  • webgl入门实例-08索引缓冲区的基本概念
  • 杂记-LeetCode中部分题思路详解与笔记-HOT100篇-其三
  • 二分查找-LeetCode
  • 代码学习总结(三)
  • 算法5-16 对二进制字符串解码
  • 多 Agent 协作怎么整:从谷歌A2A到多Agent交互方案实现
  • STL简介(了解)
  • 【无标题】
  • Qt核心知识总结
  • 第六章:6.3求一个3*3的整型矩阵对角线元素之和
  • ESP32-idf学习(二)esp32C3作服务端与电脑蓝牙数据交互
  • 机器学习有多少种算法?当下入门需要全部学习吗?
  • vscode+keil嵌入式软件开发全流程
  • C++笔记-list
  • 【已更新】2025华中杯C题数学建模网络挑战赛思路代码文章教学数学建模思路:就业状态分析与预测
  • 06-DevOps-自动构建Docker镜像
  • 动态规划专题5:最长上升子序列
  • LeetCode hot 100—括号生成
  • 数据中台(大数据平台)之数据质量管理
  • 3.Rust + Axum 提取器模式深度剖析
  • 【Python Cookbook】迭代器与生成器(一)
  • 【Qt】初识Qt(一)
  • Oracle 12.1.0.2补丁安装全流程
  • FPGA阵列
  • ZStack文档DevOps平台建设实践
  • 设计模式每日硬核训练 Day 14:组合模式(Composite Pattern)完整讲解与实战应用