友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
2560. 打家劫舍 IV
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。
示例 1：
输入：nums = [2,3,5,9], k = 2 输出：5 解释： 小偷窃取至少 2 间房屋，共有 3 种方式： - 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。 - 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。 - 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。 因此，返回 min(5, 9, 9) = 5 。
示例 2：
输入：nums = [2,7,9,3,1], k = 2 输出：2 解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。
提示：
-
1 <= nums.length <= 105 -
1 <= nums[i] <= 109 -
1 <= k <= (nums.length + 1)/2
思路分析
找出所有数上下限，然后再找出中间数 mid，使用中间数去“抢劫”，统计能打劫（金额小于中间数）的房间数量，如果数量大于 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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-17 17:04:09
*/
public int minCapability(int[] nums, int k) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
while (min <= max) {
int mid = min + (max - min) / 2;
int count = 0;
boolean visited = false;
for (int num : nums) {
if (num <= mid && !visited) {
count++;
visited = true;
} else {
visited = false;
}
}
if (count >= k) {
max = mid - 1;
} else {
min = mid + 1;
}
}
return min;
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-12-19 20:19:07
*/
public int minCapability(int[] nums, int k) {
int low = Integer.MAX_VALUE, up = Integer.MIN_VALUE;
for (int num : nums) {
low = Math.min(low, num);
up = Math.max(up, num);
}
while (low <= up) {
int mid = low + (up - low) / 2;
if (check(nums, mid, k)) {
up = mid - 1;
} else {
low = mid + 1;
}
}
return low;
}
private boolean check(int[] nums, int mid, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= mid) {
count++;
i++; // 跳过下一个，隔一个再偷
}
}
return count >= k;
}
// 深度优先遍历，超时
// public int minCapability(int[] nums, int k) {
// if (k == 1) {
// return Arrays.stream(nums).min().getAsInt();
// }
// int result = Integer.MAX_VALUE;
// for (int i = 0; nums.length - i < 2 * (k - 1) + 1; i++) {
// int next = dfs(nums, k, i, 0, result);
// if (next < 0) {
// continue;
// }
// result = Math.min(result, next);
// }
// return result;
// }
//
// private int dfs(int[] nums, int k, int start,
// int maxNum, int existedResult) {
// if (k == 0) {
// return maxNum;
// }
// if (k < 0) {
// return -1;
// }
// if (nums.length - start < 2 * (k - 1) + 1) {
// return -1;
// }
// for (int i = 2; i < nums.length; i++) {
// int next = dfs(nums, k - 1, start + i,
// Math.max(maxNum, nums[start]), existedResult);
// if (next < 0) {
// continue;
// }
// existedResult = Math.min(existedResult, next);
// }
// return existedResult;
// }