关注
个人注解:
/*主函数*/{
// 首先找出整个数组中的两个最值
for(int num : nums){
max = Math.max(max, num);
min = Math.min(min, num);
}
// 这里是采用了二分的思路,因为段的不平衡度是非严格递增的(重点),也就是有序的,故可以使用二分法
// left为0,即平衡度的最小值;right为max-min,即段为整个数组时的平衡度,此时拆分后的段的平衡度不可能超过这个值
int l = 0, r = max - min, m = 0;
while(l < r){
m = (l + r) / 2;
// 检查平衡度小于等于m的段是否存在,若存在,我们缩小右边界,看看是否存在更小的平衡度
if(check(nums, k, m)) r = m;
// 若不存在,说明需要往大于m的方向寻找
else l = m + 1;
}
// 因为left是从0开始的,而且每次只递增1,那么最后跳出时就是我们所求的结果
System.out.println(l);
}
// 是否存在满足平衡度<=x的最长的段
boolean check(int[] nums, int k, int x){
int max = nums[0], min = nums[0];
for(int i=1; i < nums.length; i++){
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
// 当平衡度大于x时,开启下一个段,看是否存在更小的平衡度。直到达到段数的限制,则返回false
if(max - min > x){
k--;
if(k <= 0) return false;
max = min = nums[i];
}
}
return k > 0;
}
查看原帖
5 3
相关推荐
投递美团等公司10个岗位 >
点赞 评论 收藏
转发
点赞 评论 收藏
转发
牛客热帖
正在热议
# 和牛牛一起刷题打卡 #
13776次浏览 1269人参与
# 通信硬件薪资爆料 #
255867次浏览 2410人参与
# 不去互联网可以去金融科技 #
3749次浏览 51人参与
# 牛客帮帮团来啦!有问必答 #
1092487次浏览 16321人参与
# 面试被问第一学历差时该怎么回答 #
18203次浏览 199人参与
# 简历中的项目经历要怎么写? #
14268次浏览 189人参与
# 工作两年想退休了 #
19247次浏览 239人参与
# 实习生应该准时下班吗 #
93145次浏览 705人参与
# 你收到了团子的OC了吗 #
530627次浏览 6293人参与
# 你已经投递多少份简历了 #
338419次浏览 4905人参与
# 简历无回复,你会继续海投还是优化再投? #
23457次浏览 329人参与
# 你怎么评价今年的春招? #
12413次浏览 193人参与
# 简历中的项目经历要怎么写 #
481928次浏览 8762人参与
# 晒一晒我的offer #
3769941次浏览 58059人参与
# 担心入职之后被发现很菜怎么办 #
39559次浏览 327人参与
# 本周投递记录 #
220885次浏览 5377人参与
# 硬件人的简历怎么写 #
81820次浏览 849人参与
# 我想象的工作vs实际工作 #
105735次浏览 1700人参与
# 2022毕业生求职现身说法 #
23608次浏览 338人参与
# 你的秋招进行到哪一步了 #
396689次浏览 6679人参与
# 产品人求职现状 #
56824次浏览 823人参与