LeetCode题目
解题分析
这类题目可能的解空间在一个范围内，不停二分遍历可能解。找到一个可行解后还要继续找，直到“最小值”的可行解。类比到二分搜索算法中就是满足条件的最左值。
以”410. 分割数组的最大值“问题为例，可能解空间在“最大的单个元素”和“所有元素和”之间。然后二分查找可行解空间，一个可行解是分组数等于或者小于目标组数。“小于目标组数”成立的原因是可以继续拆分，拆分后子数组元素和一定满足条件，显然这不一定是最优解。找到可行解后如果继续优化条件不成立，那么上一次的可行解就是最优解。
从可行解中找最左值“二分搜索”中边界条件很容易出错。比如下面找最左值的方式：
1
2
3
4
5
6
7
8
9
10
11
12
13
| while (left < right) {
int mid = left + (right - left) / 2;
int splits = split(nums, mid);
if (splits > m) {
left = mid + 1;
} else {
right = mid;
}
}
|
个人更喜欢下面的方式，容易理解，不易出错，缺点是代码有点冗余。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| while(left <= right) {
int mid = left + (right - left) / 2;
int groups = split(nums, mid);
if(groups > k) {
left = mid + 1;
} else if(groups < k) {
right = mid - 1;
} else {
if(mid == max || split(nums, mid -1) > k) {
return mid;
} else {
right = mid - 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
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| package org.stone.study.algo.ex202403;
public class SplitArrayWithMinSum {
public static void main(String[] args) {
int[] nums = new int[] {7,2,5,10,8};
int k = 2;
System.out.println("ans:" + new SplitArrayWithMinSum().splitArray(nums, k));
}
public int splitArray(int[] nums, int k) {
int max = 0, sum = 0;
for(int num : nums) {
max = Math.max(max, num);
sum += num;
}
int left = max, right = sum;
while(left <= right) {
int mid = left + (right - left) / 2;
int groups = split(nums, mid);
if(groups > k) {
left = mid + 1;
} else if(groups < k) {
right = mid - 1;
} else {
if(mid == max || split(nums, mid -1) != k) {
return mid;
} else {
right = mid - 1;
}
}
}
return left;
}
private int split(int[] nums, int maxSum) {
int curSum = 0;
int splitNum = 1;
for(int num : nums) {
if(curSum + num > maxSum) {
++splitNum;
curSum = 0;
}
curSum += num;
}
return splitNum;
}
}
|
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| package org.stone.study.algo.ex202403;
import java.util.Arrays;
public class MinEatingSpeed {
public int minEatingSpeed(int[] piles, int h) {
int max = Arrays.stream(piles).max().getAsInt();
int left = 1, right = max;
while(left <= right) {
int mid = left + (right - left) / 2;
long spent = spentHours(piles, mid);
if(spent > h) {
left = mid + 1;
} else if(spent < h){
right = mid - 1;
} else {
if(mid == 1 || spentHours(piles, mid - 1) > h) {
return mid;
} else {
right = mid - 1;
}
}
}
return left;
}
private long spentHours(int[] piles, int speed) {
long spent = 0;
for(int pile : piles) {
spent += (pile + speed - 1) / speed;
}
return spent;
}
public int minEatingSpeed2(int[] piles, int h) {
int max = 0;
for(int p : piles) {
max = Math.max(max, p);
}
int l = 1, r = max, ans = max;
while(l <= r) {
int total = 0;
int m = l + (r -l) / 2;
for(int p : piles) {
total += (p-1)/m + 1;
}
if(total > h) {
l = m + 1;
} else {
ans = m;
r = m - 1;
}
}
return ans;
}
}
|
通用的二分查找值，最左值，最右值方法请参考github
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
package org.stone.study.algo.search;
public class BinarySearch {
public int bsearch_LeftMost(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
public int bsearch_RightMost(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
else low = mid + 1;
}
}
return -1;
}
public int bsearch_GE(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
public int bsearch_LE(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}
}
|
总结
二分搜索需要数组满足单调性，简单等值搜索的场景比较少，实际场景更多是最值搜索，映射到算法中就是满足条件的最左或者最右值。这时处理算法的边界条件很重要，也是最容易出错的地方。
算法题一般不会直接让写二分搜索，需要把具体问题映射到“二分搜索”的解题思路上。比如解空间在一个单调整数数组上，找最小解等。
