題目描述:給定一個整數陣列 nums,對每個元素可以執行以下操作任意次:
求操作後陣列中 最大值 - 最小值(偏差)的最小可能值。
解題思路:
直接同時操作奇偶數會讓狀態空間爆炸。關鍵觀察是:
奇數只能乘以 2 一次就變偶數,偶數可以不斷除以 2。因此,每個奇數的「可選值」只有 {x, 2x};每個偶數的「可選值」是 {x, x/2, x/4, ...} 直到變為奇數。
統一初始狀態:先把所有奇數都乘以 2,使所有元素均為偶數。此時每個元素只能進行「除以 2」操作(向下調整)。同時記錄全域最小值 minVal。
最大堆 + 貪心收縮:
top,更新答案 ans = min(ans, top - minVal)top 為奇數(已無法再除),繼續收縮只會讓最大值不變或讓最小值增大,偏差只會擴大,故停止top 為偶數,將 top / 2 推回堆,並更新 minVal = min(minVal, top / 2)每次縮小最大值,同時追蹤最小值,持續壓縮偏差,直到最大值無法再縮小為止。
正確性:我們始終縮小最大值(減少偏差的最優操作),最小值只可能增大(除以 2),這是在局部最優下逼近全域最優的貪心策略。
時間複雜度:O(n log n · log M) — 每個元素最多被除以 2 約 log M 次(M 為最大值,M ≤ 10⁹ 故 log M ≤ 30),每次堆操作為 O(log n),共 n · log M 次操作,故為 O(n log n · log M)。
空間複雜度:O(n) — 最大堆始終存放 n 個元素。
函數 minimumDeviation(nums):
建立最大堆
minVal = 無限大
步驟 1:預處理,統一為偶數
對每個 x 在 nums 中:
若 x 為奇數:x = x * 2
將 x 加入最大堆
minVal = min(minVal, x)
ans = 無限大
步驟 2:貪心縮小最大值
無限迴圈:
top = 從最大堆彈出頂部
ans = min(ans, top - minVal)
若 top 為奇數:
跳出迴圈(已無法再縮小)
next = top / 2
將 next 加入最大堆
minVal = min(minVal, next)
回傳 ans使用 C++ multiset 同時維護最大值和最小值,避免最大堆無法直接取最小值的問題。
multiset<int> s;
for (int x : nums) {
if (x % 2 == 1) x *= 2;
s.insert(x);
}
int ans = *s.rbegin() - *s.begin();
while (*s.rbegin() % 2 == 0) {
int top = *s.rbegin();
s.erase(s.find(top));
s.insert(top / 2);
ans = min(ans, *s.rbegin() - *s.begin());
}
return ans;
邏輯相同但可以同時 O(log n) 取最大最小,程式碼更簡潔。缺點是 multiset 常數較大。
對每個元素列舉其所有可能的值(奇數有 2 個,偶數最多 log M 個),然後枚舉所有組合計算偏差。
狀態數為 ∏(各元素選擇數),指數級爆炸,僅適用於 n 極小的情況(n ≤ 5 左右)。
理論上可以二分搜尋目標偏差 d,對每個偏差值判斷是否存在可行操作方案。但判斷可行性本身需要貪心,且實作複雜度不低於直接貪心,故實際不常用。
操作限制版本:若每個元素最多只能執行一次操作(乘 2 或除 2),如何求最小偏差?此時狀態空間有限,可考慮 DP 或枚舉每個元素的「選擇」後貪心排序。
多種操作類型:若操作不只乘/除 2,還允許加減某個固定值 δ,問題如何變化?這類「可達值域」問題往往需要分析每個元素的可達區間,然後求區間重疊的最優匹配。
線上版本:若元素一個個到來(串流輸入),需要動態維護最小偏差,有序集合方案是否能高效處理插入新元素的情況?這涉及資料結構的動態維護設計。