---

1589. 所有排列中的最大和

• 标签：贪心、数组、前缀和、排序
• 难度：中等

题目链接

• 1589. 所有排列中的最大和 - 力扣

题目大意

描述：给定一个整数数组 $nums$ 和一个查询数组 $requests$，其中 $requests[i] = [start_i, end_i]$ 表示第 $i$ 个查询覆盖 $nums$ 中下标 $[start_i, end_i]$ 的元素。

可以任意排列 $nums$ 中的元素。然后计算所有查询的总和（每个查询对其覆盖范围内的元素求和，然后将所有查询的和加总）。

要求：返回在所有可能的排列中，可能获得的最大总和。结果对 $10^9 + 7$ 取模。

说明：

• $1 \le nums.length \le 10^5$。
• $0 \le nums[i] \le 10^5$。
• $1 \le requests.length \le 10^5$。

示例：

• 示例 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]。

解题思路

思路 1：差分 + 排序

1. 核心思想

每个位置 $i$ 被查询覆盖的次数决定了它对总和的贡献次数。把较大的数放在被查询次数较多的位置上，总和最大。

问题转化为：

1. 统计每个位置的被查询次数（使用差分数组）。
2. 将次数数组降序排序，$nums$ 降序排序。
3. 对应位置相乘再求和。

2. 具体步骤

第 1 步：初始化差分数组 $diff$ 长度为 $n+1$。

第 2 步：对于每个 $[l, r]$：

• $diff[l] += 1$。
• $diff[r+1] -= 1$。

第 3 步：前缀和得到每个位置的被查询次数 $cnt$。

第 4 步：$cnt$ 降序排序，$nums$ 降序排序。

第 5 步：计算 $\sum cnt[i] \times nums[i] \% MOD$。

3. 正确性证明

• 排序不等式：两个序列 $a$ 和 $b$，$\sum a_i b_i$ 最大当且仅当 $a$ 和 $b$ 同序（即同升序或同降序）。
• 这里 $a$ 是次数，$b$ 是数值，同序得最大和。

4. 举例说明

以 $nums = [1,2,3,4,5], requests = [[1,3],[0,1]]$ 为例：

• 查询覆盖次数：
  • 位置 $0$：$1$ 次（$[0,1]$）
  • 位置 $1$：$2$ 次（$[0,1],[1,3]$）
  • 位置 $2$：$1$ 次（$[1,3]$）
  • 位置 $3$：$1$ 次（$[1,3]$）
  • 位置 $4$：$0$ 次
• 次数排序：$[2,1,1,1,0]$
• $nums$ 排序：$[5,4,3,2,1]$
• 最大和：$2\times5 + 1\times4 + 1\times3 + 1\times2 + 0\times1 = 19$

思路 1：代码

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        n = len(nums)
        diff = [0] * (n + 1)

        for l, r in requests:
            diff[l] += 1
            diff[r + 1] -= 1

        cnt = [0] * n
        cur = 0
        for i in range(n):
            cur += diff[i]
            cnt[i] = cur

        cnt.sort(reverse=True)
        nums.sort(reverse=True)

        ans = 0
        for i in range(n):
            ans = (ans + cnt[i] * nums[i]) % MOD

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \log n)$，排序。
• 空间复杂度：$O(n)$。