題目描述:給定 k 個已升序排序的整數串列,找出最小範圍 [a, b](b - a 最小,若相等取 a 較小者),使得每個串列中至少有一個元素落在此範圍內。
解題思路(最小堆 + 追蹤最大值):
核心觀察:有效的範圍 [min, max] 必須從每個串列各取至少一個元素。若我們固定「範圍的最小值」(即堆中最小元素),則範圍的最大值就是當前在堆中所有元素的最大值。因此問題轉化為:滑動所有串列的「指針」,使範圍 [最小元素, 目前最大元素] 盡量小。
演算法步驟:
初始化:將每個串列的第一個元素加入最小堆,格式為 (value, listIdx, elemIdx)。同時記錄 curMax = 所有初始元素中的最大值,以及初始最佳答案 [heap.top().value, curMax]。
主迴圈:
(minVal, i, j),當前候選範圍為 [minVal, curMax]。lists[i] 的下一個元素 lists[i][j+1] 加入堆,並更新 curMax(新元素可能更大)。lists[i] 已無下一個元素,表示無法再維持「每個串列各有代表」,終止迴圈。終止:當某個串列耗盡時停止,返回最佳答案。
時間複雜度:O(N log k),其中 N 為所有串列元素總數,k 為串列數量 — 每個元素最多入堆一次,每次堆操作 O(log k)(堆中最多 k 個元素),故總體 O(N log k)。
空間複雜度:O(k) — 堆中同時最多存 k 個元素(每個串列各一個代表),故空間 O(k)。
Function smallestRange(nums):
k = number of lists
minHeap = empty min-heap of (value, listIdx, elemIdx)
curMax = -infinity
// Step 1: Initialize with first element of each list
For i from 0 to k-1:
Push (nums[i][0], i, 0) into minHeap
curMax = max(curMax, nums[i][0])
bestLeft = heap minimum value
bestRight = curMax
// Step 2: Slide the window
While true:
(minVal, i, j) = pop minimum from minHeap
// Current range is [minVal, curMax]
If (curMax - minVal) < (bestRight - bestLeft):
OR same size but minVal < bestLeft:
bestLeft = minVal, bestRight = curMax
If j + 1 >= size of nums[i]:
Break // list i exhausted, cannot maintain coverage
nextVal = nums[i][j+1]
Push (nextVal, i, j+1) into minHeap
curMax = max(curMax, nextVal)
Return [bestLeft, bestRight]排序展平 + 滑動窗口 O(N log N):將所有元素標記所屬串列後合併排序,再用滑動窗口維護一個覆蓋所有 k 個串列的最小窗口(類似 LeetCode 76「最小覆蓋子字串」)。需要雜湊表計數各串列在窗口內的元素數量。時間複雜度 O(N log N),空間 O(N),常數比堆解法大。
合併排序視角:最小堆解法本質上是 k 路合併(merge k sorted lists)的過程中,同步追蹤最大值。兩個思路可以互相轉換理解。
暴力枚舉 O(N² · k):枚舉所有可能的左右端點對,對每個端點對檢查是否覆蓋所有串列。實際上不可行(N 可達 50000),但可用於驗證小測資的正確性。
[a, b] 不一定包含矩陣中的實際元素(即 a、b 可以是任意實數),問題的答案是否會改變?