house-robber-iv

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes.

The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed.

You are given an integer array <code>nums</code> representing how much money is stashed in each house. More formally, the <code>ith</code> house from the left has <code>nums[i]</code> dollars.

You are also given an integer <code>k</code>, representing the minimum number of houses the robber will steal from. It is always possible to steal at least <code>k</code> houses.

Return the minimum capability of the robber out of all the possible ways to steal at least <code>k</code> houses.

&nbsp;
Example 1:

<pre>
Input: nums = [2,3,5,9], k = 2
Output: 5
Explanation: 
There are three ways to rob at least 2 houses:
- Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5.
- Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9.
- Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9.
Therefore, we return min(5, 9, 9) = 5.
</pre>

Example 2:

<pre>
Input: nums = [2,7,9,3,1], k = 2
Output: 2
Explanation: There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= (nums.length + 1)/2</code></li>
</ul>

minCapability

House Robber IV

Container With Most Water

container-with-most-water

盛最多水的容器

House Robber

house-robber

打家劫舍

Array

Binary Search

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

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

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

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

另给你一个整数&nbsp;<code>k</code> ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 <code>k</code> 间房屋。

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

&nbsp;

示例 1：

<pre>
输入：nums = [2,3,5,9], k = 2
输出：5
解释：
小偷窃取至少 2 间房屋，共有 3 种方式：
- 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。
- 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。
- 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。
因此，返回 min(5, 9, 9) = 5 。
</pre>

示例 2：

<pre>
输入：nums = [2,7,9,3,1], k = 2
输出：2
解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= (nums.length + 1)/2</code></li>
</ul>