class Solution {
public:
int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
}
};
1589. 所有排列中的最大和
有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [starti, endi] 。第 i 个查询求 nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi] 的结果 ，starti 和 endi 数组索引都是 从 0 开始 的。
你可以任意排列 nums 中的数字，请你返回所有查询结果之和的最大值。
由于答案可能会很大，请你将它对 109 + 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.length1 <= n <= 1050 <= nums[i] <= 1051 <= requests.length <= 105requests[i].length == 20 <= starti <= endi < n原站题解
php 解法, 执行用时: 612 ms, 内存消耗: 90.4 MB, 提交时间: 2023-09-18 09:52:00
class Solution {
/**
* @param Integer[] $nums
* @param Integer[][] $requests
* @return Integer
*/
function maxSumRangeQuery($nums, $requests) {
$freq = array_fill(0, count($nums)+1, 0);
// 查询中每个边界点出现的频率
for ( $i = 0; $i < count($requests); $i++ ) {
$freq[$requests[$i][0]]++;
$freq[$requests[$i][1]+1]--;
}
//
for ( $i = 1; $i < count($nums); $i++ ) {
$freq[$i] += $freq[$i-1];
}
$freq = array_slice($freq, 0, count($freq) - 1);
sort($freq);
sort($nums);
$ans = 0;
for ( $i = 0; $i < count($nums); $i++ ) {
$ans += $nums[$i] * $freq[$i];
}
return $ans % 1000000007;
}
}
golang 解法, 执行用时: 252 ms, 内存消耗: 11.2 MB, 提交时间: 2023-09-18 09:46:36
func maxSumRangeQuery(nums []int, requests [][]int) int {
freq := make([]int, len(nums)+1)
for i := 0; i < len(requests); i++ {
freq[requests[i][0]]++
freq[requests[i][1]+1]--
}
for i := 1; i < len(nums); i++ {
freq[i] += freq[i-1]
}
freq = freq[:len(freq)-1]
sort.Ints(freq)
sort.Ints(nums)
ans := 0
for i := 0; i < len(nums); i++ {
ans += nums[i] * freq[i]
}
return ans % 1000000007
}
java 解法, 执行用时: 23 ms, 内存消耗: 64.7 MB, 提交时间: 2023-09-18 09:45:36
class Solution {
public int maxSumRangeQuery(int[] nums, int[][] requests) {
final int MODULO = 1000000007;
int length = nums.length;
int[] counts = new int[length];
for (int[] request : requests) {
int start = request[0], end = request[1];
counts[start]++;
if (end + 1 < length) {
counts[end + 1]--;
}
}
for (int i = 1; i < length; i++) {
counts[i] += counts[i - 1];
}
Arrays.sort(counts);
Arrays.sort(nums);
long sum = 0;
for (int i = length - 1; i >= 0 && counts[i] > 0; i--) {
sum += (long) nums[i] * counts[i];
}
return (int) (sum % MODULO);
}
}
cpp 解法, 执行用时: 484 ms, 内存消耗: 131.7 MB, 提交时间: 2023-09-18 09:45:14
class Solution {
public:
int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
int MODULO = 1000000007;
int length = nums.size();
auto counts = vector<int>(length);
for (auto request: requests) {
int start = request[0], end = request[1];
counts[start]++;
if (end + 1 < length) {
counts[end + 1]--;
}
}
for (int i = 1; i < length; i++) {
counts[i] += counts[i - 1];
}
sort(counts.begin(), counts.end());
sort(nums.begin(), nums.end());
long long sum = 0;
for (int i = length - 1; i >= 0 && counts[i] > 0; i--) {
sum += (long long)nums[i] * counts[i];
}
return sum % MODULO;
}
};
python3 解法, 执行用时: 240 ms, 内存消耗: 42.9 MB, 提交时间: 2023-09-18 09:44:48
'''
贪心
每次查询的范围都是一个子数组，因此可以根据查询数组 requests 计算得到数组 nums 的
每个下标位置被查询的次数。题目要求返回所有查询结果之和的最大值，当查询结果之和最
大时，应满足数组 nums 中的越大的数字被查询的次数越多，因此可以使用贪心算法求解。
'''
class Solution:
def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
MODULO = 10**9 + 7
length = len(nums)
counts = [0] * length
for start, end in requests:
counts[start] += 1
if end + 1 < length:
counts[end + 1] -= 1
for i in range(1, length):
counts[i] += counts[i - 1]
counts.sort()
nums.sort()
total = sum(num * count for num, count in zip(nums, counts))
return total % MODULO