Medium

题目描述

给你一个整数数组 nums 和一个正整数 k。返回所有最多包含 k 个元素的 nums 子序列的最大值和最小值之和。

由于答案可能很大，请返回对 10^9 + 7 取模的结果。

示例 1：

输入：nums = [1,2,3], k = 2
输出：24
解释：
最多包含 2 个元素的 nums 子序列有：

| 子序列 | 最小值 | 最大值 | 和 |
|--------|--------|--------|-----|
| [1]    | 1      | 1      | 2   |
| [2]    | 2      | 2      | 4   |
| [3]    | 3      | 3      | 6   |
| [1, 2] | 1      | 2      | 3   |
| [1, 3] | 1      | 3      | 4   |
| [2, 3] | 2      | 3      | 5   |
| 总计   |        |        | 24  |

示例 2：

输入：nums = [5,0,6], k = 1
输出：22
解释：
对于只有 1 个元素的子序列，最小值和最大值都是元素本身。因此总和是 5 + 5 + 0 + 0 + 6 + 6 = 22。

示例 3：

输入：nums = [1,1,1], k = 2
输出：12
解释：
子序列 [1, 1] 和 [1] 各出现 3 次。对于所有这些序列，最小值和最大值都是 1。因此总和是 12。

约束条件：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 1 <= k <= min(70, nums.length)

解题思路

这道题要求计算所有最多包含k个元素的子序列的最大值和最小值之和。关键观察是：对于排序后的数组，如果我们能计算每个元素作为最大值和最小值出现的次数，就能得到答案。

解题思路：

  1. 排序数组：首先将数组排序，这样便于分析每个元素在子序列中的作用。

  2. 分别计算最大值和最小值的贡献：

    • 对于元素 nums[i] 作为最大值：它必须被选中，且只能从前 i+1 个元素中选择其他元素
    • 对于元素 nums[i] 作为最小值：它必须被选中，且只能从后 n-i 个元素中选择其他元素

  3. 组合数计算：使用组合数学计算每个元素作为最大值/最小值的子序列数量

    • 元素 i 作为最大值的子序列数：sum(C(i, j)) for j from 0 to min(k-1, i)
    • 元素 i 作为最小值的子序列数：sum(C(n-i-1, j)) for j from 0 to min(k-1, n-i-1)

  4. 优化计算：预计算组合数，避免重复计算，并使用模运算处理大数。

这种方法的时间复杂度是 O(n*k)，空间复杂度是 O(k²)，能够有效处理给定的约束条件。

代码实现

class Solution {
public:
    int minMaxSums(vector<int>& nums, int k) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        
        sort(nums.begin(), nums.end());
        
        // 预计算组合数
        vector<vector<long long>> C(n + 1, vector<long long>(k + 1, 0));
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= min(i, k); j++) {
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
            }
        }
        
        // 预计算前缀和
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= min(i, k - 1); j++) {
                prefix[i] = (prefix[i] + C[i][j]) % MOD;
            }
        }
        
        long long result = 0;
        
        for (int i = 0; i < n; i++) {
            // nums[i] 作为最大值的贡献
            long long maxContrib = (1LL * nums[i] * prefix[i]) % MOD;
            result = (result + maxContrib) % MOD;
            
            // nums[i] 作为最小值的贡献
            long long minContrib = (1LL * nums[i] * prefix[n - i - 1]) % MOD;
            result = (result + minContrib) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        nums.sort()
        
        # 预计算组合数
        C = [[0] * (k + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            C[i][0] = 1
            for j in range(1, min(i + 1, k + 1)):
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
        
        # 预计算前缀和
        prefix = [0] * (n + 1)
        for i in range(n + 1):
            for j in range(min(i + 1, k)):
                prefix[i] = (prefix[i] + C[i][j]) % MOD
        
        result = 0
        
        for i in range(n):
            # nums[i] 作为最大值的贡献
            max_contrib = (nums[i] * prefix[i]) % MOD
            result = (result + max_contrib) % MOD
            
            # nums[i] 作为最小值的贡献
            min_contrib = (nums[i] * prefix[n - i - 1]) % MOD
            result = (result + min_contrib) % MOD
        
        return result

public class Solution {
    public int MinMaxSums(int[] nums, int k) {
        const int MOD = 1000000007;
        int n = nums.Length;
        
        Array.Sort(nums);
        
        // 预计算组合数
        long[,] C = new long[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            C[i, 0] = 1;
            for (int j = 1; j <= Math.Min(i, k); j++) {
                C[i, j] = (C[i-1, j-1] + C[i-1, j]) % MOD;
            }
        }
        
        // 预计算前缀和
        long[] prefix = new long[n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= Math.Min(i, k - 1); j++) {
                prefix[i] = (prefix[i] + C[i, j]) % MOD;
            }
        }
        
        long result = 0;
        
        for (int i = 0; i < n; i++) {
            // nums[i] 作为最大值的贡献
            long maxContrib = ((long)nums[i] * prefix[i]) % MOD;
            result = (result + maxContrib) % MOD;
            
            // nums[i] 作为最小值的贡献
            long minContrib = ((long)nums[i] * prefix[n - i - 1]) % MOD;
            result = (result + minContrib) % MOD;
        }
        
        return (int)result;
    }
}

var minMaxSums = function(nums, k) {
    const MOD = 1e9 + 7;
    const n = nums.length;
    
    nums.sort((a, b) => a - b);
    
    // 预计算组合数
    const C = Array(n + 1).fill(null).map(() => Array(k + 1).fill(0));
    for (let i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (let j = 1; j <= Math.min(i, k); j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
    
    // 预计算前缀和
    const prefix = Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= Math.min(i, k - 1); j++) {
            prefix[i] = (prefix[i] + C[i][j]) % MOD;
        }
    }
    
    let result = 0;
    
    for (let i = 0; i < n; i++) {
        // nums[i] 作为最大值的贡献
        const maxContrib = (nums[i] * prefix[i]) % MOD;
        result = (result + maxContrib) % MOD;
        
        // nums[i] 作为最小值的贡献
        const minContrib = (nums[i] * prefix[n - i - 1]) % MOD;
        result = (result + minContrib) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n×k)
空间复杂度O(n×k)

说明：

  • 时间复杂度：排序需要 O(n log n)，预计算组合数需要 O(n×k)，计算结果需要 O(n)，总体为 O(n×k)
  • 空间复杂度：存储组合数表需要 O(n×k) 空间，前缀和数组需要 O(n) 空间