Skip to content

Latest commit

 

History

History
156 lines (117 loc) · 5.96 KB

3428.maximum-and-minimum-sums-of-at-most-size-k-subsequences.md

File metadata and controls

156 lines (117 loc) · 5.96 KB

题目地址(3428. 至多 K 个子序列的最大和最小和 - 力扣（LeetCode）)

题目描述

给你一个整数数组 nums 和一个整数 k，请你返回一个整数，表示从数组中选取 至多 k 个子序列，所有可能方案中，子序列的 最大值之和 加上 最小值之和 的结果。由于结果可能很大，请返回对 (10^9 + 7) 取模后的值。

一个数组的 子序列 是指通过删除一些（可以是 0 个）元素后剩下的序列，且不改变其余元素的相对顺序。例如，[1, 3] 是 [1, 2, 3] 的子序列，而 [2, 1] 不是。

示例 1：

输入：nums = [1,2,3], k = 2
输出：12
解释：
所有可能的至多 k=2 个子序列方案：
- 空子序列 []：最大值和最小值都记为 0
- [1]：最大值 1，最小值 1
- [2]：最大值 2，最小值 2
- [3]：最大值 3，最小值 3
- [1,2]：最大值 2，最小值 1
- [1,3]：最大值 3，最小值 1
- [2,3]：最大值 3，最小值 2
- [1,2,3]：最大值 3，最小值 1
最大值之和 = 0 + 1 + 2 + 3 + 2 + 3 + 3 + 3 = 17
最小值之和 = 0 + 1 + 2 + 3 + 1 + 1 + 2 + 1 = 11
总和 = 17 + 11 = 28 % (10^9 + 7) = 28
由于 k=2，实际方案数不会超过 k，但这里考虑了所有子序列，结果仍正确。

示例 2：

输入：nums = [2,2], k = 3
输出：12
解释：
所有可能的至多 k=3 个子序列方案：
- []：最大值 0，最小值 0
- [2]（第一个）：最大值 2，最小值 2
- [2]（第二个）：最大值 2，最小值 2
- [2,2]：最大值 2，最小值 2
最大值之和 = 0 + 2 + 2 + 2 = 6
最小值之和 = 0 + 2 + 2 + 2 = 6
总和 = 6 + 6 = 12 % (10^9 + 7) = 12

提示：

  • (1 \leq nums.length \leq 10^5)
  • (1 \leq nums[i] \leq 10^9)
  • (1 \leq k \leq 10^5)

前置知识

  • 组合数学：组合数 (C(n, m)) 表示从 (n) 个元素中选 (m) 个的方案数。
  • 贡献法

思路

这道题要求计算所有至多 (k) 个子序列的最大值之和与最小值之和。数组的顺序对每个元素的贡献没有任何影响，因此我们可以先对数组进行排序，然后计算每个元素作为最大值或最小值的贡献。

我们可以从贡献的角度来思考：对于数组中的每个元素，它在所有可能的子序列中作为最大值或最小值的次数是多少？然后将这些次数乘以元素值，累加起来即可。

分析

  1. 子序列的性质：

    • 一个子序列的最大值是其中最大的元素，最小值是最小的元素。
    • 对于一个有序数组 (nums)，若元素 (nums[i]) 是子序列的最大值，则子序列只能从 (nums[0]) 到 (nums[i]) 中选取，且必须包含 (nums[i])。
    • 若 (nums[i]) 是子序列的最小值，则子序列只能从 (nums[i]) 到 (nums[n-1]) 中选取，且必须包含 (nums[i])。

  2. 组合计数：

    • 假设数组已排序（从小到大），对于 (nums[i])：
      • 作为最大值的子序列：从前 (i) 个元素中选 (j) 个（(0 \leq j < \min(k, i+1))），再加上 (nums[i])，总方案数为 (\sum_{j=0}^{\min(k, i)} C(i, j))。
      • 作为最小值的子序列：从后 (n-i-1) 个元素中选 (j) 个（(0 \leq j < \min(k, n-i))），再加上 (nums[i])，总方案数为 (\sum_{j=0}^{\min(k, n-i-1)} C(n-i-1, j))。
    • 这里 (C(n, m)) 表示组合数，即从 (n) 个元素中选 (m) 个的方案数。

  3. 优化组合计算：

    • 由于 (n) 和 (k) 可达 (10^5)，直接用 (math.comb) 会超时，且需要取模。
    • 使用预计算阶乘和逆元的方法，快速计算 (C(n, m) = n! / (m! \cdot (n-m)!) \mod (10^9 + 7))。

  4. 最终公式：

    • 对每个 (nums[i])，计算其作为最大值的贡献和最小值的贡献，累加后取模。

步骤

  1. 对数组 (nums) 排序。
  2. 预计算阶乘 (fac[i]) 和逆元 (inv_f[i])。
  3. 遍历 (nums)：
    • 计算 (nums[i]) 作为最大值的次数，乘以 (nums[i])，加到答案中。
    • 计算 (nums[i]) 作为最小值的次数，乘以 (nums[i])，加到答案中。
  4. 返回结果对 (10^9 + 7) 取模。

代码

代码支持 Python3：

Python3 Code:

MOD = int(1e9) + 7

# 预计算阶乘和逆元
MX = 100000
fac = [0] * MX  # fac[i] = i!
fac[0] = 1
for i in range(1, MX):
    fac[i] = fac[i - 1] * i % MOD

inv_f = [0] * MX  # inv_f[i] = i!^-1
inv_f[-1] = pow(fac[-1], -1, MOD)
for i in range(MX - 1, 0, -1):
    inv_f[i - 1] = inv_f[i] * i % MOD

# 计算组合数 C(n, m)
def comb(n: int, m: int) -> int:
    if m < 0 or m > n:
        return 0
    return fac[n] * inv_f[m] * inv_f[n - m] % MOD

class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        nums.sort()  # 排序，便于计算最大值和最小值贡献
        ans = 0
        n = len(nums)
        
        # 计算每个元素作为最大值的贡献
        for i, x in enumerate(nums):
            s = sum(comb(i, j) for j in range(min(k, i + 1))) % MOD
            ans += x * s
            
        # 计算每个元素作为最小值的贡献
        for i, x in enumerate(nums):
            s = sum(comb(n - i - 1, j) for j in range(min(k, n - i))) % MOD
            ans += x * s
            
        return ans % MOD

复杂度分析

  • 时间复杂度：(O(n \log n + n \cdot k))
    • 排序：(O(n \log n))。
    • 预计算阶乘和逆元：(O(MX))，(MX = 10^5) 是常数。
    • 遍历 (nums) 并计算组合和：(O(n \cdot k))，因为对于每个 (i)，需要计算最多 (k) 个组合数。
  • 空间复杂度：(O(MX))，用于存储阶乘和逆元数组。

总结

这道题的关键在于理解子序列的最大值和最小值的贡献，并利用组合数学计算每个元素出现的次数。预计算阶乘和逆元避免了重复计算组合数的开销，使得代码能在时间限制内运行。排序后分别处理最大值和最小值贡献，是一个清晰且高效的思路。

如果你有其他解法或疑问，欢迎讨论！