[LeetCode解题报告] 1589. 所有排列中的最大和

[LeetCode解题报告] 1589. 所有排列中的最大和

• • 一、 题目
  • • 1. 题目描述
    • 2. 原题链接
  • 二、 解题报告
  • • 1. 思路分析
    • 2. 复杂度分析
    • 3. 代码实现
  • 三、 本题小结
  • 四、 参考链接

一、 题目 1. 题目描述

有一个整数数组 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.length
• 1 <= n <= 105
• 0 <= nums[i] <= 105
• 1 <= requests.length <= 105
• requests[i].length == 2
• 0 <= starti <= endi < n

Related Topics

• 贪心
• 数组
• 前缀和
• 排序

• 👍 51
• 👎 0

2. 原题链接

链接: 1589. 所有排列中的最大和

二、 解题报告 1. 思路分析

1. 题意实际上是需要访问次数越大的位置，放个越大的值。

• 那么由于数据范围是10^5,我们可以用树状数组计算每个点的访问次数。
• 对访问次数和原数组都逆序排序，对应的位置放对应的数计算即可。
  复杂度O(nlgn)。

2. 前缀和思路：
   实际上树状数组的IUPQ模型是基于差分数组的:

• sum(l,r,v)：对差分数组区间两端 *** 作。
• get(index)：相当于求差分数组截止index的前缀和。
  树状数组是为了查询任意区间的，这题我们只需要前缀和，那么可以去掉树状数组的lgN。
  直接展开差分数组做。
  当然可以优化掉差分数组的那层空间，直接计算freq。

2. 复杂度分析

最坏时间复杂度O(nlog₂n)

3. 代码实现

树状数组`

class BinIndexTree:
    def __init__(self, size):
        self.size = size
        self.bin_tree = [0 for _ in range(size+5)]
    def add(self,i,v):
        while i<=self.size :
            self.bin_tree[i] += v
            i += self.lowbit(i)
    def update(self,i,v):
        val = v - (self.sum(i)-self.sum(i-1))
        self.add(i,val)
    def sum(self,i):
        s = 0
        while i >= 1:
            s += self.bin_tree[i]
            i -= self.lowbit(i)
        return s
    def lowbit(self,x):
        return x&-x
    def _point_query(self,i):
   		return self.sum(i)
    def _interval_add(self,l,r,v):
   		self.add(l,v)
   		self.add(r+1,-v)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        mod = 10**9+7
        nums.sort(reverse=True)
        tree = BinIndexTree(n+5)
        for start,end in requests:
            tree._interval_add(start+1,end+1,1)
        freq = [0] * n
        for i in range(n):
            freq[i] = tree._point_query(i+1)
        ans = 0
        freq.sort(reverse=True)
        for i in range(n):
            if freq[i] ==0:
                break
            ans += freq[i]*nums[i]%mod
            ans %= mod        
        return ans

差分数组

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        mod = 10**9+7
        nums.sort(reverse=True)
        diff = [0]*(n+1)
        
        for start,end in requests:
            diff[start] += 1
            diff[end+1] -= 1
        freq = [0] * n
        s = 0
        for i in range(n):
            s += diff[i]
            freq[i] = s
        ans = 0
        freq.sort(reverse=True)
        for i in range(n):
            if freq[i] ==0:
                break
            ans += freq[i]*nums[i]%mod
            ans %= mod
        
        return ans

差分数组省去空间开销

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        mod = 10**9+7
        nums.sort(reverse=True)
        diff = [0]*(n+1)
        
        for start,end in requests:
            diff[start] += 1
            diff[end+1] -= 1
        freq = [0] * n
        s = 0
        for i in range(n):
            s += diff[i]
            freq[i] = s
        ans = 0
        freq.sort(reverse=True)
        for i in range(n):
            if freq[i] ==0:
                break
            ans += freq[i]*nums[i]%mod
            ans %= mod
        
        return ans

三、 本题小结

1. 前缀和差分数组的结合。

四、 参考链接

• 链接: [英雄星球六月集训LeetCode解题日报] 第八日 前缀和