狒狒吃香蕉

思路：最小值为1，最大值就是数组最大值。在这个范围上不断二分。遇到能吃完记录答案，往左侧二分寻找更小的，吃不完往不计答案，右侧二分寻找更大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int minEatingSpeed(int[] piles, int h) {
    int l=1;
    int r = 0;
    for (int i : piles) {
        r = Math.max(r,i);
    }
    int ans = r;
    while(l<=r){
        int mid = l + ((r-l)>>1);
        if(fMinEatingSpeed(piles,mid) <= h){
            ans = mid;
            r = mid-1;
        }else {
            l = mid+1;
        }
    }
    return ans;
}

public long fMinEatingSpeed(int[] piles,int speed){
    long cnt = 0 ;
    for (int pile : piles) {
        cnt += (pile + speed - 1) / speed;
    }
    return cnt;
}

分割数组最大值

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组，使得这 k 个子数组各自和的最大值 最小。

返回分割后最小的和的最大值。

子数组 是数组中连续的部份。

思路： 对答案进行二分，答案范围为[0,sum(nums)]。f函数为当最小值为limit的时候，我需要的最小划分数。如果这个最小划分数<=k,则记录答案，并且去左侧二分，寻找更小的答案。反之，则去右侧二分，不记录答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public static int splitArray(int[] nums, int k) {
	long sum = 0;
	for (int num : nums) {
		sum += num;
	}
	long ans = 0;
	// [0,sum]二分
	for (long l = 0, r = sum, m, need; l <= r;) {
		// 中点m
		m = l + ((r - l) >> 1);
		// 必须让数组每一部分的累加和 <= m，请问划分成几个部分才够!
		need = f(nums, m);
		if (need <= k) {
			// 达标
			ans = m;
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
	return (int) ans;
}

// 必须让数组arr每一部分的累加和 <= limit，请问划分成几个部分才够!
// 返回需要的部分数量
public static int f(int[] arr, long limit) {
	int parts = 1;
	int sum = 0;
	for (int num : arr) {
		if (num > limit) {
			return Integer.MAX_VALUE;
		}
		if (sum + num > limit) {
			parts++;
			sum = num;
		} else {
			sum += num;
		}
	}
	return parts;
}

找出第k小的数对距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static int smallestDistancePair(int[] nums, int k) {
	int n = nums.length;
	Arrays.sort(nums);
	int ans = 0;
	// [0, 最大-最小]，不停二分
	for (int l = 0, r = nums[n - 1] - nums[0], m, cnt; l <= r;) {
		// m中点，arr中任意两数的差值 <= m
		m = l + ((r - l) >> 1);
		// 返回数字对的数量
		cnt = f(nums, m);
		if (cnt >= k) {
			ans = m;
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
	return ans;
}

// arr中任意两数的差值 <= limit
// 这样的数字配对，有几对？
public static int f(int[] arr, int limit) {
	int ans = 0;
	// O(n)
	for (int l = 0, r = 0; l < arr.length; l++) {
		// l......r r+1
		while (r + 1 < arr.length && arr[r + 1] - arr[l] <= limit) {
			r++;
		}
		// arr[l...r]范围上的数差值的绝对值都不超过limit
		// arr[0...3]
		// 0,1
		// 0,2
		// 0,3
		ans += r - l;
	}
	return ans;
}

同时运行n台电脑的最长时间

leelcode2141

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟。你想使用这些电池让 全部 n 台电脑 同时 运行。

一开始，你可以给每台电脑连接 至多一个电池 。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。

注意，你不能给电池充电。

请你返回你可以让 n 台电脑同时运行的 最长 分钟数。

思路：还是二分答案。答案范围是[0,sum(batteries)]。f函数为当运行时间为m的时候，我能运行的最多电脑数量。如果这个数量大于等于规定的数量，那么我记录mid,然后去右边二分，寻找更长的时间。反之，不计入答案，去左侧二分。 还有一个贪心优化，可以减少二分的次数。详见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public long maxRunTime(int n, int[] batteries) {
        int len = batteries.length;
        if(len<n){
            return 0;
        }
        long l = 0;
        long r =0;
        int max = 0;

        for(int i =0;i<len;i++){
            r+=batteries[i];
            max= Math.max(max,batteries[i]);
        }
        if (r> (long) max * n) {
            // 所有电池的最大电量是max
            // 如果此时sum > (long) max * n，
            // 说明 : 最终的供电时间一定在 >= max，而如果最终的供电时间 >= max
            // 说明 : 对于最终的答案X来说，所有电池都是课上讲的"碎片拼接"的概念
            // 那么寻找 ? * n <= sum 的情况中，尽量大的 ? 即可
            // 即sum / n
            return r / n;
        }
        long ans = 0;
        r = max;
        while(l<=r){
            long mid = l+((r-l)>>1);
            int num = f(batteries,mid);
            if(num >= n ){
                ans = mid;
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return ans;
    }

    public int f(int[] batteries,long maxTime){
        if(maxTime == 0){
            return Integer.MAX_VALUE;
        }
        long litterTime = 0;
        int ans = 0;
        for(int i =0;i<batteries.length;i++){
            if(batteries[i]<maxTime){
                litterTime+=batteries[i];
            }else {
                ans++;
            }
        }
        ans += (int) (litterTime/maxTime);
        return ans;
    }

二分总结

二分答案法，其实都可以看成给了三个变量，数组，限制以及答案。正向推导需要我们根据数组以及限制得到答案。但现在根据二分答案法，我们可以先把答案确定下来，然后算出一个跟限制相关的东西，把这个东西跟原限制作比较（这里就观察单调性），来判断下一步应该去哪边找答案。

总结
总结