【力扣每日一题】2023.9.10 打家劫舍Ⅳ

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

题目翻译有些烂，我来二次翻译一下，找出数组中k个两两互不相邻的数，求出它们的最大值。要求最大值尽可能小。

我们换个看法来解题，实际上我们要找出一个数，在数组中小于等于这个数并且两两不相邻的元素需要大于等于k。

这下子就让我想到了九月七号的每日一题修车的最少时间和LeetCode75的第五十六题爱吃香蕉的珂珂，可以使用二分查找来解题。

我们用二分查找，首先需要确认左右范围，我们要找的数是数组中长度为k的子数组的最大值，所以范围就是整个数组的最小值和最大值，我们一次遍历就可以获取（用api调用获取也可以）。

接着就是判断缩小范围的条件。

我们去数组中寻找数组中符合要求的小于等于范围中位数的数有几个。如果数量大于等于k，那么缩小右范围，反之缩小左范围，直到范围缩小到一个数，那么这个数就是我们要求的答案。

寻找的话我们可以直接遍历整个数组，遇到不比范围中位数大的数我们就记录下来，然后把用于遍历的下标再加个1，表示不取相邻的元素。

具体可以参考代码。

代码：

class Solution {
public:
    //查看数组中是否有不相邻的k个小于等于窃取能力的房屋
    bool check(vector<int>&nums,int k,int mid){
        int n=0;
        for(int i=0;isize();i++){
            if(nums[i]<=mid){
                n++;i++;//因为需要不相邻,所以i++多一次
            }
        }
        return n>=k;
    }
    int minCapability(vector<int>& nums, int k) {
        int l=INT_MAX,r=INT_MIN;
        //获取最小值和最大值来作为二分查找的左右边界
        for(int num:nums){
            l=min(l,num);
            r=max(r,num);
        }
        while(l
            int mid=l+(r-l)/2;
            if(check(nums,k,mid)) r=mid;
            else l=mid+1;
        }
        return l;
    }
};