2560. 打家劫舍 IV

难度：中等

思路：

1. 最小化最大值问题，显然问题额答案在 [min(nums), max(nums)] 之间，二分搜索答案即可
2. 如何寻找小于 x 的所有可窃取房屋的数量？贪心遍历，对于第 i 间房屋只要 nums[i] < x 且 i - 1 间房屋没有被偷取过，那么第 i 间房屋是必定偷取的。
3. 简单地来说，反证法，如果第 i 间房屋可偷但是不偷，那么必然是为了偷第 i + 1 间房屋（第 i + 2 间房屋不受第 i 间房屋影响），那么如果第 i + 2 间房屋不可偷则第 i 间和 i + 1 间偷哪间都可以不影响最后的总数，如果第 i + 2 间房屋可偷，那么显然为了偷 i + 1 间房屋会导致 i 和 i + 2 都偷不了，显然这是不对的。

代码：

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        l, r = min(nums), max(nums)
        while l < r:
            mid = (l + r) >> 1
            n = 0
            vis = 0
            for i in nums:
                if i <= mid and vis == 0:
                    n += 1
                    vis = 1
                else:
                    vis = 0
            if n < k:
                l = mid + 1
            else:
                r = mid
        
        return l
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

python有自带的二分查找函数bisect_left(list, x, key=None)
其中第一个参数是待插入值的列表
第二个参数是待插入的值
第三个参数表示更复杂的比较方式
个人对key参数的理解，相当于把二分查找过程中的 mid 值传入 key 函数中，将最后的返回值再与待插入值 x 进行比较

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        def f(y : int) -> int:
            count, visited = 0, False
            for x in nums:
                if x <= y and not visited:
                    count, visited = count + 1, True
                else:
                    visited = False
            return count
        return bisect_left(range(min(nums), max(nums)), k, key = f) + min(nums)
1
2
3
4
5
6
7
8
9
10
11