题目
给你两个下标从 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} 中删除若干元素得到的剩余集合，也可以不删除任何元素。
示例 1：
输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3 输出：12 解释： 四个可能的子序列分数为： - 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。 - 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。 - 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。 - 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。 所以最大分数为 12 。
示例 2：
输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1 输出：30 解释： 选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。
提示：
n == nums1.length == nums2.length1 <= n <= 1050 <= nums1[i], nums2[j] <= 1051 <= k <= n
题解（自己想完全没有头绪，只想到了暴力）
- 根据各位网友的题解大概整理了一下思路。
- 首先因为暴力搜索的时间复杂度太高了，所以尝试使用贪心的思路来考虑问题。
- 接着根据nums1和nums2两部分计算的复杂度来看，先把nums2的最小值固定了再求nums1是比较合理的顺序。
- 那么怎么确定nums2的最小值呢？因为我们要求的是两部分的乘积最大，那么不妨就把nums2部分贪心地从大到小取，那么对应下标的nums1的和就得出来了。
- 然后不断地往小的倍数扩展，并替换掉原组合中的最小值，这样就大概率会扩大了。（其实这应该算是一步剪枝操作）。
- 直到把剩余的nums2的部分都遍历完了，最后的最大值就是全局最大值了。
代码复现
复杂度分析
- 时间复杂度：走遍历的过程中需要更新小根堆，所以总的额时间复杂度是O(nlogn)。
- 空间复杂度：O(n)，堆和数组的元素个数。
知识积累
- 思路确实很有巧思，真的暴露了我数据结构和算法都不过关的短板了。
- 先来讲讲新学的一些数据结构和代码表达方式把。
- priority_queue<type, store_type, cmp>三个参数分别表示元素的数据类型，存储元素的数据结构类型，元素间的比较方法。底层的实现逻辑是通过堆来实现的（堆怎么实现我还没去看，到时候再说），所以插入、删除和查询的时间复杂度都是O(logn)的。
- 然后lambda表达式，太久没写了都已经忘记怎么写了orz。
- 这是一种内嵌匿名函数的写法，其形式示例为：[ ]({形参}) { 函数体 }，这样就可以省去额外显式定义一个函数的操作了。
- 另外，在结构体内部定义比较函数，并将其传给数据结构或者排序函数作为判断标准时，需将该比较函数定义为静态函数。