Date
Sep 7, 2023
need_review
need_review
type
undo
undo
难度
中等
给你一个整数数组
ranks ，表示一些机械工的 能力值 。ranks_i 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n^2 分钟内修好 n 辆车。同时给你一个整数
cars ，表示总共需要修理的汽车数目。请你返回修理所有汽车 最少 需要多少时间。
注意：所有机械工可以同时修理汽车。
示例 1：
示例 2：
提示：
1 <= ranks.length <= 10^5
1 <= ranks[i] <= 100
1 <= cars <= 10^6
解法1
使用双指针代表时间, 二分查找.
left取最小=1; right随便取一个rank中的元素计算出单人修所有车的时间.
需要得到的是修好所有车最少的时间
需要注意:
- 如果时间t内可以修完所有车, 那么大于等于t都可以修完所有车
- 如果时间t内不能修完, 那么小于等于t都不能
能力值为
r 的机械工可以在 r * n^2 分钟内修好 n 辆车 → 枚举时间 t , 使 → 能力值为 r 的工人可以修完 辆汽车. 如果所有工人能在t时间内修完的车数量和大于等于cars → 说明车能在t时间内修完 → 可以压缩时间 → 右指针左移, 即右指针=t , 否则: 左指针右移, 即左指针=t+1
时间复杂度, n为工人数量, L为二分查找的上界. 空间复杂度
