# 2560. House Robber IV
###### tags: `Leetcode` `Medium` `Binary Search` `Greedy`
Link: https://leetcode.com/problems/house-robber-iv/description/
## 思路
思路参考[这里](https://leetcode.com/problems/house-robber-iv/solutions/3143697/java-c-python-binary-search-o-1-space/)
“**When we mini-max one capacity to do something, (here is robber k houses) we can use bianry search.**”

binary search by value
每一个mid值都是目前假定的min capability 我们要检查在它的基础上能偷多少房子
那么如何检查能偷多少房子呢
这时候就要用到greedy
从前往后扫描 如果当前```num<=mid``` 说明可以偷 那就偷 ```take+=1``` 由于如果偷了当前房子 下一个房子就不能偷了 所以```i++```
为什么这样能保证偷房子数最多呢 因为假设```nums[0]```和```nums[1]```都小于等于```mid``` 如果偷```nums[0]``` 接下来可以选择的范围是```nums[2:n-1]``` 而如果偷```nums[1]``` 接下来可以选择的范围是```nums[3:n-1]``` 所以显然选前面一个
## Code

class Solution {
    public int minCapability(int[] nums, int k) {
        int left = Integer.MAX_VALUE, right = 0;
        for(int i=0; i<nums.length; i++){
            left = Math.min(left, nums[i]);
            right = Math.max(right, nums[i]);
        }
        while(left<right){
            int take = 0;
            int mid = left+(right-left)/2;
            for(int i=0; i<nums.length; i++){
                if(nums[i]<=mid){
                    take += 1;
                    i += 1;
                }
            }
            if(take<k) left = mid+1;
            else right = mid;
        }
        return left;
    }
}