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 nums representing how much money is stashed in each house. More formally, the ith house from the left has nums[i] dollars.
You are also given an integer k, representing the minimum number of houses the robber will steal from. It is always possible to steal at least k houses.
Return the minimum capability of the robber out of all the possible ways to steal at least k 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.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= (nums.length + 1)/2
Solution 1: Binary Search + DP
It’s easy to see that higher capability means more houses we can rob. Thus this can be formulate as a binary search algorithm e.g. find the minimum C s.t. we can rob at least k houses.
Then we can use dp(i) to calculate maximum houses we can rob if starting from the i’th house.
dp(i) = max(1 + dp(i + 2) if nums[i] <= C else 0, dp(i + 1))
Time complexity: O(n log m)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { public: int minCapability(vector<int>& nums, int k) { int l = 0; int r = *max_element(begin(nums), end(nums)) + 1; vector<int> cache(nums.size(), -1); function<int(int, int)> rob = [&](int m, int i) -> int { if (i >= nums.size()) return 0; if (cache[i] >= 0) return cache[i]; if (nums[i] > m) return rob(m, i + 1); return cache[i] = max(1 + rob(m, i + 2), rob(m, i + 1)); }; while (l < r) { int m = l + (r - l) / 2; fill(begin(cache), end(cache), -1); if (rob(m, 0) >= k) r = m; else l = m + 1; } return l; } }; |
Solution 2: Binary Search + Greedy
From: dp(i) = max(1 + dp(i + 2) if nums[i] <= C else 0, dp(i + 1)) we can see that if we can pick the i-th one, it will be the same or better if we skip and start from dp(i + 1). Thus we can convert this from DP to greedy. As long as we can pick the current one, we pick it first.
Time complexity: O(n log m)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: int minCapability(vector<int>& nums, int k) { int l = 0; int r = *max_element(begin(nums), end(nums)) + 1; auto rob = [&](int m) -> int { int ans = 0; for (int i = 0; i < nums.size(); ++i) if (nums[i] <= m) { ++ans; ++i; } return ans; }; while (l < r) { int m = l + (r - l) / 2; if (rob(m) >= k) r = m; else l = m + 1; } return l; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment