从一个范围内选择最多整数 II
难度:
标签:
题目描述
代码结果
运行时间: 137 ms, 内存: 31.5 MB
/**
* LeetCode Problem 2557: 从一个范围内选择最多整数 II
* 题目描述:
* 给定一个整数数组 arr 和一个整数范围 [low, high],找出可以从该范围内选择的最多整数,使它们的和最大。
*
* 题目思路:
* 1. 使用 Java Stream 过滤出范围 [low, high] 内的整数。
* 2. 对过滤出的整数进行排序,以便我们可以从大到小选择元素来最大化总和。
* 3. 使用流的终端操作累加这些数直到达到范围的上限 high。
*/
import java.util.Arrays;
public class Solution {
public int maxSumInRange(int[] arr, int low, int high) {
return Arrays.stream(arr)
.filter(num -> num >= low && num <= high)
.boxed()
.sorted((a, b) -> b - a)
.reduce(0, (sum, num) -> (sum + num <= high) ? sum + num : sum);
}
}
解释
方法:
该题解的思路是通过二分搜索找出最大的x,使得1到x的和(减去在这个范围内的被禁止的数字)不超过maxSum。具体步骤如下:
1. 将禁止的数字列表进行去重和排序。
2. 使用accumulate和chain函数计算从1到每个禁止数字的累积和,以便后续快速计算。
3. 定义一个辅助函数over来检查给定的x值是否导致总和超过maxSum。这个函数计算从1到x的总和,并根据x的值,从累积和列表中减去被禁止的数字的总和。
4. 使用二分搜索找到第一个使over函数返回True的x值,这个x值之前的数字即是可选的最大整数。
5. 最后的返回值是x减去在x之前的被禁止数字的数量,得到实际可以使用的最大整数。
时间复杂度:
O(m log m + log n * log m)
空间复杂度:
O(m)
代码细节讲解
🦆
为什么在计算1到x的和时使用了公式`x*(1+x)//2`而不是迭代或其他方法?
▷🦆
函数`over`中`bisect_right`的作用是什么,它是如何帮助判断给定的x值是否合适的?
▷🦆
在二分搜索中使用`bisect_left`查找第一个使`over`函数返回True的x值,这种方法是否会在某些情况下返回错误的x值?
▷