打家劫舍(4)(2023-09-19)

打家劫舍(4)

题目

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统,所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上,从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数 k ,表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

题目分析

这里的核心是找到最少能偷的K间房
设x是预设的偷窃能力
f(x)是在x的偷窃能力下,能够偷的房屋
随着x的增大,f(x)总是能保持增加或者相等
我们只需要找到这个搜索能力值,并且满足f(x)正好小于k的情况