題目資訊

• 題目編號: 2560
• 題目連結: House Robber IV
• 主題: Array, Binary Search

題目敘述

有數棟房子沿著一條街道排列，每棟房子裡面都有一些錢。現在有一名強盜，想從這些房子中偷錢，但是他拒絕從相鄰的房子偷。

強盜的能力是指他從他偷過的所有房子中單棟房子所能偷到的最多金額。

給定一個整數陣列 nums，代表每棟房子裡藏有多少錢。更正式的說，第 $i$ 棟房子有 nums[i] 美元。

你也會得到一個整數 k，代表強盜至少要偷的房子數量。至少偷 k 棟房子總是可能的。

返回所有可能的偷竊方式中，強盜的最低能力，即偷至少 k 棟房子的方法中，能力的最小值。

例子 1:

輸入: nums = [2,3,5,9], k = 2
輸出: 5
解釋: 
有三種方法可以偷至少兩棟房子：
- 偷第 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。

例子 2:

輸入: nums = [2,7,9,3,1], k = 2
輸出: 2
解釋: 有 7 種偷房子的方式。導致最低能力的方式是偷第 0 和第 4 棟房子。返回 max(nums[0], nums[4]) = 2。

約束:

• $1 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$
• $1 \leq k \leq (nums.length + 1)/2$

直覺

此問題是一個經典的資源優化問題，目標是在鄰近的房屋不能被搶劫的條件下，最大化搶劫的收入。此外，問題還要求優化最小能力值，這個能力值被定義為任何一個房屋所偷取的最大金額。在這裡使用二分搜尋法來尋找此最優的能力值是一個具有吸引力的選擇，因為我們在檢驗一個閾值。

複雜性在於需要選擇至少 k 個非鄰近的房屋並使得能力值最小。此處的二分搜尋法並不是傳統意義上的尋找特定值，而是尋找最小可行的能力值。

解法

此解法可以分為兩個主要部分：驗證給定能力值是否可行的輔助函數 check，以及找出最小可能能力值的二分搜尋機制。

1. 輔助函數 check:

   • 該函數用來驗證是否能在不超過給定 test 能力的情況下搶劫至少 k 間房屋。
   • 此函數遍歷每間房屋，檢查該房屋中的金額是否小於或等於 test。如果是，則認為這間房已被搶劫，減少計數 k，並跳過鄰近的房屋。
   • 該過程持續進行，直到我們成功計劃搶劫 k 間房屋，或房屋已經耗盡，以確認 test 能力是否足夠。

2. 最小能力值的二分搜尋法:

   • 該方法透過類似二分搜尋的方式來有效縮小最小能力值。
   • 將 ans 初始化為 -1，作為起始點。
   • 使用 nums 中的最大值作為二分搜尋的起始跳躍步，因為能力值不需要超過房屋中最大的藏金。
   • 將此跳躍逐步減半，類似於傳統二分搜尋中對搜尋空間的折半。
   • 對於每個 ans + jump 的值，使用 check 函數驗證是否能在此能力下搶劫 k 間房屋。如果不可行，則將 ans 增加 jump。
   • 當跳躍步驟減至 0 時，搜尋結束，確保 ans + 1 提供最小足夠的能力值。

此方法有效地在時間複雜度上進行權衡，利用了 check 中的線性掃描以及 minCapability 中的對數調整，最終的總時間複雜度由 $O(n \log m)$ 驅動，其中 $n$ 是房屋的數量，$m$ 是最大的金額值。

程式碼

C++

class Solution {
public:
    // 函式用來檢查在強盜能力不大於 `test` 的情況下，是否有可能搶劫至少 `k` 間房子。
    bool check(vector<int>& nums, int k, int test) {
        // 遍歷所有房子。
        for (int i = 0; i < nums.size(); i++) {
            // 如果當前的房子可以在給定的能力範圍內被搶劫。
            if (nums[i] <= test) {
                k--; // 減少需要搶劫的房子數量。
                i++; // 略過相鄰的房子。
            }
        }
        // 如果至少可以搶劫 `k` 間房子，則返回 true。
        return (k <= 0);
    }

    // 函式用來確定搶劫至少 `k` 間房子所需的最小能力。
    int minCapability(vector<int>& nums, int k) {
        int ans = -1; // 初始化答案變數。

        // 使用類似二分搜尋的方法來尋找最小的能力。
        for (int jump = *max_element(nums.begin(), nums.end()); jump > 0; jump >>= 1) {
            // 嘗試是否有可能在當前 `ans + jump` 的情況下實現。
            while (!check(nums, k, ans + jump)) {
                ans += jump; // 增加能力。
            }
        }

        // 結果需要加 1 以獲得正確的最小能力。
        return ans + 1;
    }
};

Python

class Solution:
    # 函式用來檢查在搶匪的能力小於等於 `test` 的情況下
    # 是否有可能搶劫至少 `k` 間房子。
    def check(self, nums, k, test):
        # 遍歷所有房子。
        i = 0
        while i < len(nums):
            # 如果當前房子可以在給定的能力範圍內搶劫。
            if nums[i] <= test:
                k -= 1  # 減少需要搶劫的房子數量。
                i += 1  # 略過相鄰的房子。
            i += 1
        # 如果至少可以搶劫 `k` 間房子則返回 true。
        return k <= 0

    # 函式用來確定搶劫至少 `k` 間房子所需的最小能力。
    def minCapability(self, nums, k):
        ans = -1  # 初始化答案變數。

        # 使用類似二分搜尋的方法來找到最小能力。
        jump = max(nums)
        while jump > 0:
            # 嘗試檢查在當前 `ans + jump` 的情況下是否可能。
            while not self.check(nums, k, ans + jump):
                ans += jump  # 增加能力。
            jump >>= 1

        # 結果需要加 1 以獲得正確的最小能力。
        return ans + 1

複雜度分析

• 時間複雜度：函數 minCapability 的時間複雜度為 $O(n \log M)$，其中 $n$ 是 nums 的長度，$M$ 是 nums 中的最大值。原因如下：

  • minCapability 中的外層循環對可能的能力範圍執行二分搜尋，這需要 $O(\log M)$ 次迭代。

  • 在二分搜尋的每次迭代中，都會呼叫 check 函數，該函數具有 $O(n)$ 的線性時間複雜度，因為它會遍歷整個 nums 列表一次。

  因此，整體時間複雜度是這兩個因素的乘積：$O(n \log M)$。

• 空間複雜度：空間複雜度為 $O(1)$，因為無論輸入大小如何，演算法只使用恆定量的額外空間。唯一使用的額外儲存空間是幾個整數變數，這不依賴於 nums 或 k 的大小。操作和檢查都是原地進行的，不需要與輸入大小成比例的任何額外空間。