建造街区的最短时间
难度:
标签:
题目描述
代码结果
运行时间: 31 ms, 内存: 16.1 MB
/*
* 思路:
* 1. 使用Java Stream对blocks进行排序。
* 2. 使用PriorityQueue来管理blocks的建造顺序。
* 3. 每次取出最小的两个元素,并将其相加后放回队列中,直至队列中只剩一个元素。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int minBuildTime(int[] blocks, int split) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.stream(blocks).boxed().collect(Collectors.toList()));
while (pq.size() > 1) {
int first = pq.poll();
int second = pq.poll();
pq.offer(second + split);
}
return pq.poll();
}
}
解释
方法:
题解采用二分查找和贪心算法的组合。首先对blocks数组进行排序,以便使用贪心策略。定义一个辅助函数check(x),该函数用来判断是否可以在时间x内完成所有blocks的建造。在check函数中,使用一个贪心的方法,模拟以时间x为限制条件下的工作流程。如果在时间x内可以完成建造,返回True;否则返回False。在主函数中,通过二分查找的方法,寻找满足条件的最小时间x。
时间复杂度:
O(n log(max(blocks)))
空间复杂度:
O(n)
代码细节讲解
🦆
在`check`函数中,为何选择从blocks数组的最大值开始处理,而不是从最小值开始?
▷🦆
在二分查找过程中,如何确定初始的`right`值为1000000?这个值是否基于特定的条件或假设?
▷🦆
在`check`函数中,当`工人数翻倍`后,为什么还需要检查`i >= 0 and t + split > x - blocks[i]`?这一步的逻辑是基于什么考虑?
▷🦆
题解中提到,如果工人数`s`小于0则返回False,但根据代码逻辑,`s`似乎是以1开始且只会翻倍,何时会出现`s`小于0的情况?
▷