【力扣题解】1589. 所有排列中的最大和

😊博主目前也在学习，有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈

文章目录

• • 一、题目
  • • 1、题目描述
    • 2、基础框架
    • 3、原题链接
  • 二、解题报告
  • • 1、思路分析
    • 2、代码详解
  • 三、本题知识

一、题目

1、题目描述

有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [starti, endi] 。第 i 个查询求 nums[starti] + nums[starti + 1] + … + nums[endi - 1] + nums[endi] 的结果 ，starti 和 endi 数组索引都是 从 0 开始 的。

你可以任意排列 nums 中的数字，请你返回所有查询结果之和的最大值。

由于答案可能会很大，请你将它对 109 + 7 取余 后返回。

2、基础框架

• Java版本框架代码如下：

class Solution {    public int maxSumRangeQuery(int[] nums, int[][] requests) { }}

3、原题链接

1589. 所有排列中的最大和

二、解题报告

1、思路分析

       (1)若想返回值最大，只需要把出现频率最大的位置放上最大的数即可。
       (2)在统计每个数出现频率的时候，如果直接暴力法统计，在数据多的时候会超时，所以这里用前缀和统计。定义diff数组统计频率。遍历requests数组，在requests[i][0]到requests[i][1]区间内的频率都需要加一，但是如果只让diff[requests[i][0]]++，在用前缀和计算的时候会导致requests[i][0]后面的频率都加一，这个结果不是我们想要的，所以我们需要在requests[i][1] + 1 减一，这样requests[i][1] 后数的频率就不会加一。
       (3)将最大频率乘以最大值累加即可。

2、代码详解

class Solution {    public int maxSumRangeQuery(int[] nums, int[][] requests) { long ans = 0; int n = requests.length; int[] diff = new int[nums.length]; for(int i = 0;i < n;i++) {     diff[requests[i][0]]++;     if(requests[i][1] + 1 < nums.length) {  diff[requests[i][1] + 1]--;     }   } for(int i = 1;i < diff.length;i++) {     diff[i] += diff[i - 1]; } Arrays.sort(nums); Arrays.sort(diff); for(int i = 0;i < nums.length;i++) {     ans = (ans + (long)diff[i]*nums[i])%1000000007; } return (int)ans;    }}

三、本题知识

前缀和

美国云服务器