875. 爱吃香蕉的珂珂

发表于 | 分类于
二分法求下边界

用时：60min

拿到题目最快能想到的思路是枚举所有吃完香蕉的速度，找到能吃完香蕉的最小的速度。

枚举的速度范围是[1… 最大堆的香蕉],因为速度不会小于1，也没有速度比最大香蕉堆更快的必要

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var minEatingSpeed = function(piles, h) {
  // 枚举所有可以吃完香蕉的速度,找到最小的
  piles = piles.sort((a,b) => a - b)
  var maxSpeed = piles[piles.length - 1]
  var min = maxSpeed
  for(let i = 1; i <= maxSpeed; i ++) {
    var H = 0
    for(let j = 0 ; j < piles.length; j ++) {
      H += Math.ceil(piles[j] / i)
    }
    if(H <= h) {
      min = Math.min(min,i)
    }
  }
  return min
};

随即可以想到，[1… 最大速度]是一个单调区间，可以用二分法来解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var minEatingSpeed = function(piles, h) {
  // 最小速度就是求下界l
  piles = piles.sort((a,b) => a - b)
  var maxSpeed = piles[piles.length - 1]
  var min = maxSpeed
  // 对速度区间 [1... maxSpeed] 做二分
  var l = 1 ,r = maxSpeed
  while(l <= r) {
    var mid = l + Math.floor ((r - l) / 2)
    var H = 0
    for(let j = 0 ; j < piles.length ; j ++) {
      H += Math.ceil(piles[j] / mid)
    }
    if ( H <= h ) {
      // 符合，试试速度是否可以更小
      r = mid - 1
    } else {
      // 不符合，增加速度
      l = mid + 1
    }
  }
  return l
};