HardRating 2093

632. Smallest Range Covering Elements from K Lists

arrayhash-tablegreedysliding-windowsortingheap-priority-queue

解題說明

Smallest Range Covering Elements from K Lists

題目描述：給定 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] 已無下一個元素，表示無法再維持「每個串列各有代表」，終止迴圈。
終止：當某個串列耗盡時停止，返回最佳答案。

C++ 解法

複雜度分析

時間複雜度：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 可以是任意實數），問題的答案是否會改變？
若 k 個串列未排序，我們需要先排序嗎？排序後複雜度如何變化？
本題的滑動窗口變體（排序展平後）和 LeetCode 76「最小覆蓋子字串」的解題框架有何相似之處？能否寫出通用的「覆蓋 k 類別最小窗口」模板？

解題說明

Smallest Range Covering Elements from K Lists

解題思路（最小堆 + 追蹤最大值）：

演算法步驟：

初始化：將每個串列的第一個元素加入最小堆，格式為 (value, listIdx, elemIdx)。同時記錄 curMax = 所有初始元素中的最大值，以及初始最佳答案 [heap.top().value, curMax]。
主迴圈：
- 彈出堆中最小元素 (minVal, i, j)，當前候選範圍為 [minVal, curMax]。
- 若此範圍比目前最佳範圍更小（或同等大小但左端點更小），更新最佳答案。
- 將 lists[i] 的下一個元素 lists[i][j+1] 加入堆，並更新 curMax（新元素可能更大）。
- 若 lists[i] 已無下一個元素，表示無法再維持「每個串列各有代表」，終止迴圈。
終止：當某個串列耗盡時停止，返回最佳答案。

複雜度分析

空間複雜度：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]

其他解法

合併排序視角：最小堆解法本質上是 k 路合併（merge k sorted lists）的過程中，同步追蹤最大值。兩個思路可以互相轉換理解。

延伸思考

若允許範圍 [a, b] 不一定包含矩陣中的實際元素（即 a、b 可以是任意實數），問題的答案是否會改變？
若 k 個串列未排序，我們需要先排序嗎？排序後複雜度如何變化？
本題的滑動窗口變體（排序展平後）和 LeetCode 76「最小覆蓋子字串」的解題框架有何相似之處？能否寫出通用的「覆蓋 k 類別最小窗口」模板？