Medium

题目描述

我们有一个整数数组 nums，和一个请求数组 requests，其中 requests[i] = [starti, endi]。第 i 个请求询问 nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi] 的和。starti 和 endi 都是基于 0 的索引。

返回所有 nums 排列中所有请求的最大总和。

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

示例 1：

输入：nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
输出：19
解释：nums 的一个排列是 [2,1,3,4,5]，结果如下：
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
总和：8 + 3 = 11。
一个总和更高的排列是 [3,5,4,2,1]，结果如下：
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5 = 8
总和：11 + 8 = 19，这是你能做的最好的。

示例 2：

输入：nums = [1,2,3,4,5,6], requests = [[0,1]]
输出：11
解释：具有最大总和的排列是 [6,5,4,3,2,1]，请求和为 [11]。

示例 3：

输入：nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
输出：47
解释：具有最大总和的排列是 [4,10,5,3,2,1]，请求和为 [19,18,10]。

约束：

  • n == nums.length
  • 1 <= n <= 10^5
  • 0 <= nums[i] <= 10^5
  • 1 <= requests.length <= 10^5
  • requests[i].length == 2
  • 0 <= starti <= endi < n

解题思路

这是一个典型的贪心算法问题。为了最大化所有请求的总和，我们需要将最大的数字放在被访问次数最多的位置上。

解题思路：

  1. 统计频次：首先统计每个索引位置在所有请求中被访问的频次。可以使用差分数组来高效计算区间更新。

  2. 贪心策略：将频次最高的位置分配给最大的数字，频次次高的位置分配给次大的数字，以此类推。这样能保证总和最大。

  3. 实现步骤：

    • 使用差分数组统计每个位置的访问频次
    • 对频次数组和原数组分别排序
    • 将排序后的数组按对应顺序相乘求和

算法复杂度分析：

  • 时间复杂度：O(n log n + m)，其中 n 是数组长度，m 是请求数量。排序操作占主要时间
  • 空间复杂度：O(n)，用于存储频次数组

这种贪心策略是最优的，因为我们总是让贡献最大的元素去乘以最大的频次，从而获得全局最优解。

代码实现

class Solution {
public:
    int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
        int n = nums.size();
        vector<int> freq(n, 0);
        
        // 使用差分数组统计每个位置的频次
        for (auto& req : requests) {
            freq[req[0]]++;
            if (req[1] + 1 < n) {
                freq[req[1] + 1]--;
            }
        }
        
        // 将差分数组转换为实际频次
        for (int i = 1; i < n; i++) {
            freq[i] += freq[i - 1];
        }
        
        // 排序：频次降序，数组降序
        sort(freq.begin(), freq.end(), greater<int>());
        sort(nums.begin(), nums.end(), greater<int>());
        
        // 计算最大和
        long long result = 0;
        const int MOD = 1e9 + 7;
        for (int i = 0; i < n; i++) {
            result = (result + (long long)freq[i] * nums[i]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        freq = [0] * n
        
        # 使用差分数组统计每个位置的频次
        for start, end in requests:
            freq[start] += 1
            if end + 1 < n:
                freq[end + 1] -= 1
        
        # 将差分数组转换为实际频次
        for i in range(1, n):
            freq[i] += freq[i - 1]
        
        # 排序：频次降序，数组降序
        freq.sort(reverse=True)
        nums.sort(reverse=True)
        
        # 计算最大和
        result = 0
        MOD = 10**9 + 7
        for i in range(n):
            result = (result + freq[i] * nums[i]) % MOD
        
        return result

public class Solution {
    public int MaxSumRangeQuery(int[] nums, int[][] requests) {
        int n = nums.Length;
        int[] freq = new int[n];
        
        // 使用差分数组统计每个位置的频次
        foreach (var req in requests) {
            freq[req[0]]++;
            if (req[1] + 1 < n) {
                freq[req[1] + 1]--;
            }
        }
        
        // 将差分数组转换为实际频次
        for (int i = 1; i < n; i++) {
            freq[i] += freq[i - 1];
        }
        
        // 排序：频次降序，数组降序
        Array.Sort(freq, (a, b) => b.CompareTo(a));
        Array.Sort(nums, (a, b) => b.CompareTo(a));
        
        // 计算最大和
        long result = 0;
        const int MOD = 1000000007;
        for (int i = 0; i < n; i++) {
            result = (result + (long)freq[i] * nums[i]) % MOD;
        }
        
        return (int)result;
    }
}

var maxSumRangeQuery = function(nums, requests) {
    const n = nums.length;
    const freq = new Array(n).fill(0);
    
    // 使用差分数组统计每个位置的频次
    for (const [start, end] of requests) {
        freq[start]++;
        if (end + 1 < n) {
            freq[end + 1]--;
        }
    }
    
    // 将差分数组转换为实际频次
    for (let i = 1; i < n; i++) {
        freq[i] += freq[i - 1];
    }
    
    // 排序：频次降序，数组降序
    freq.sort((a, b) => b - a);
    nums.sort((a, b) => b - a);
    
    // 计算最大和
    let result = 0;
    const MOD = 1e9 + 7;
    for (let i = 0; i < n; i++) {
        result = (result + freq[i] * nums[i]) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n + m)其中 n 是数组长度，m 是请求数量。排序操作 O(n log n)，处理请求 O(m)
空间复杂度O(n)用于存储频次数组