什麼是「單調性」呢?考慮一個函數 P,如果 s 滿足條件,那麼 P(s) = 1,反之則為 0。如果 P 有單調性,我們就說這個問題有單調性。這樣的好處是,我們可以直接用前面的方法二分搜出要求的 s。如果計算 P 的複雜度並不大時,這樣的方法可以有非常的表現效率。在你沒辦法快速求出 s 而只能快速確認一個 s 是否符合條件時,這是一個非常好的方法。
intminEatingSpeed(vector<int>& piles, int h) {
int max =*max_element(piles.begin(), piles.end());
if (piles.size() == h)
return max;
int left =1, right = max +1;
while (left < right){
int mid = left + (right-left)/2;
if (canFinish(piles, mid, h)){
right = mid;
} else {
left = mid +1;
}
}
return left;
}
boolcanFinish(vector<int> piles, int speed, int h){
int time =0;
for (int n : piles){
time += n/speed + ((n % speed >0) ?1:0);
}
return time <= h;
}