#藍橋#JAVA#打家劫舍4
題目描述
沿街有一排連續的房屋。每間房屋內都藏有一定的現金。現在有一位小偷計劃從這些房屋中竊取現金。
由于相鄰的房屋裝有相互連通的防盜系統，所以小偷?不會竊取相鄰的房屋?。
小偷的?竊取能力?定義為他在竊取過程中能從單間房屋中竊取的?最大金額?。
給你一個整數數組?nums?表示每間房屋存放的現金金額。形式上，從左起第?i?間房屋中放有?nums[i]?美元。
另給你一個整數?k?，表示竊賊將會竊取的?最少?房屋數。小偷總能竊取至少?k?間房屋。
返回小偷的?最小?竊取能力。
示例 1：
輸入：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 。
解題思路
本題采用二分查找算法來高效地找出滿足條件的最小能力值。二分查找的前提是問題的解空間具有單調性，在本題中，能力值越大，能夠偷取的不相鄰房屋數量就可能越多，因此可以利用二分查找不斷縮小可能的能力值范圍，直到找到最小的滿足條件的能力值。
具體步驟
1. 確定二分查找的左右邊界
- 左邊界?
lower：通過?Arrays.stream(nums).min().getAsInt()?找出數組?nums?中的最小值。這是因為最小的能力值至少要能夠偷取到數組中金額最小的房屋。 - 右邊界?
upper：通過?Arrays.stream(nums).max().getAsInt()?找出數組?nums?中的最大值。這是因為最大的能力值最多為數組中金額最大的房屋的金額。
2. 二分查找過程
- 使用?
while(lower <= upper)?循環進行二分查找，只要左邊界小于等于右邊界，就繼續查找。 - 在每次循環中，計算當前左右邊界的中間值?
middle，作為本次猜測的能力值。
3. 檢查當前能力值是否滿足條件
- 初始化計數器?
count?為 0，用于記錄在當前能力值下可以偷取的不相鄰房屋的數量。 - 初始化布爾變量?
visited?為?false，用于標記上一個房屋是否被偷取。 - 遍歷數組?
nums?中的每個元素?x：- 如果?
x <= middle?且?!visited，說明當前房屋的金額小于等于當前猜測的能力值，并且上一個房屋沒有被偷取，此時可以偷取當前房屋，將?count?加 1，并將?visited?標記為?true。 - 否則，將?
visited?標記為?false，表示當前房屋不被偷取。
- 如果?
4. 根據檢查結果調整二分查找的邊界
- 如果?
count >= k，說明在當前能力值下可以偷取到至少?k?個不相鄰的房屋，當前能力值可能過大，將右邊界?upper?更新為?middle - 1，縮小查找范圍。 - 否則，說明當前能力值過小，將左邊界?
lower?更新為?middle + 1，擴大查找范圍。
5. 返回結果
- 當二分查找結束后，左邊界?
lower?即為滿足條件的最小能力值，將其返回。
class Solution {public int minCapability(int[] nums, int k) {int lower = Arrays.stream(nums).min().getAsInt();// 使用 Java 8 的 Stream API 對數組 nums 進行操作// Arrays.stream(nums) 將數組轉換為流// min() 方法找出流中的最小值// getAsInt() 方法將 OptionalInt 類型的結果轉換為 int 類型// 最終將數組中的最小值賦給變量 lower，作為二分查找的左邊界int upper = Arrays.stream(nums).max().getAsInt();// 同樣使用 Stream API// max() 方法找出流中的最大值// getAsInt() 方法將結果轉換為 int 類型// 把數組中的最大值賦給變量 upper，作為二分查找的右邊界while(lower <= upper){// 開始二分查找的循環，只要左邊界小于等于右邊界，就繼續循環int middle = (lower + upper)/2;// 計算當前左右邊界的中間值，作為本次猜測的能力值int count = 0;// 初始化一個計數器 count，用于記錄在當前能力值下可以偷取的房屋數量boolean visited = false;// 初始化一個布爾變量 visited，用于標記上一個房屋是否被偷取for(int x :nums){// 遍歷數組 nums 中的每個元素 xif(x <= middle&&!visited){// 如果當前房屋的金額 x 小于等于當前猜測的能力值 middle，并且上一個房屋沒有被偷取count ++;// 則偷取當前房屋，計數器 count 加 1visited = true;// 標記當前房屋已被偷取}else{visited = false;// 否則，標記當前房屋未被偷取}}if(count >= k){// 如果在當前能力值下可以偷取的房屋數量 count 大于等于要求的數量 kupper = middle -1;// 說明當前能力值可能過大，將右邊界 upper 更新為 middle - 1，縮小查找范圍}else{lower = middle+1;// 否則，說明當前能力值過小，將左邊界 lower 更新為 middle + 1，擴大查找范圍}}return lower;// 當二分查找結束后，左邊界 lower 即為滿足條件的最小能力值，將其返回}
}同時，利用二分法這里給出了更優的解決方案
class Solution {public int minCapability(int[] nums, int k) {int n = nums.length;int max = 0, min = Integer.MAX_VALUE;// 初始化 max 為 0，用于存儲數組中的最大值// 初始化 min 為 Integer.MAX_VALUE，用于存儲數組中的最小值for(int x:nums){// 遍歷數組 nums 中的每個元素 xif(x < min) min = x;// 如果當前元素 x 小于 min，則更新 min 為 xif(x > max) max = x;// 如果當前元素 x 大于 max，則更新 max 為 x}int left = min, right = max;// 初始化二分查找的左邊界 left 為數組的最小值// 初始化二分查找的右邊界 right 為數組的最大值while(left <= right){// 開始二分查找的循環，只要左邊界小于等于右邊界，就繼續查找int mid = left + right >> 1;// 計算當前左右邊界的中間值 mid，作為本次猜測的能力值// 這里使用位運算 >> 1 代替除以 2，以提高計算效率int count = 0;// 初始化計數器 count，用于記錄在當前能力值下可以偷取的房屋數量for(int i = 0; i < n; ++i){// 遍歷數組 numsif(nums[i] <= mid){// 如果當前房屋的金額 nums[i] 小于等于當前猜測的能力值 midif(++count == k)break;// 先將計數器 count 加 1，若加 1 后 count 等于 k，說明已經找到了 k 個滿足條件的房屋，退出循環++i;// 跳過下一個房屋，確保偷取的房屋不相鄰}}if(count >= k)right = mid - 1;// 如果在當前能力值下可以偷取的房屋數量 count 大于等于 k，說明當前能力值可能過大，將右邊界 right 更新為 mid - 1，縮小查找范圍elseleft = mid + 1;// 否則，說明當前能力值過小，將左邊界 left 更新為 mid + 1，擴大查找范圍}return left;// 當二分查找結束后，左邊界 left 即為滿足條件的最小能力值，將其返回}
}
