LC.P2560[打家劫舍IV]

方法一：二分查找+动态规划

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
class Solution {
    public int minCapability(int[] nums, int k) {
        int left = 0, right = 0;
        for (int x : nums) {
            right = Math.max(right, x);
        }
        while (left < right) {
            int mid = left + right >>> 1;
            if (check(nums, k, mid)) right = mid;
            else left = mid + 1;
        }
        return right;
    }

    private boolean check(int[] nums, int k, int max) {
        int f0 = 0, f1 = 0;
        for (int x : nums) {
            if (x > max) {
                f0 = f1;
            } else {
                int tmp = f1;
                f1 = Math.max(f1, f0 + 1);
                f0 = tmp;
            }
        }
        return f1 >= k;
    }
}
  • 时间复杂度：$O(nlogM)$，其中$M = max(nums)$
  • 空间复杂度：$O(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
class Solution {
    public int minCapability(int[] nums, int k) {
        int left = 0, right = 0;
        for (int x : nums) {
            right = Math.max(right, x);
        }
        while (left < right) {
            int mid = left + right >>> 1;
            if (check(nums, k, mid)) right = mid;
            else left = mid + 1;
        }
        return right;
    }

    private boolean check(int[] nums, int k, int max) {
        int cnt = 0, n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= max) {
                ++cnt; // 偷 nums[i]
                ++i; // 跳过下一间房子
            }
        }
        return cnt >= k;
    }
}
  • 时间复杂度：$O(nlogM)$，其中$M = max(nums)$
  • 空间复杂度：$O(1)$