#2560
House Robber IV
specialist · 640 · lc medium +30 · verified · 64.8% accepted · 1,710 likes · top 68%
Description
A robber must choose at least k non-adjacent houses from the array nums to rob. The robber's capability equals the maximum value stolen from any single house. Return the minimum possible capability over all valid selections of at least k non-adjacent houses.
Example 1:
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.
Example 2:
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.
Code
1
2
3