632。 kのリストの要素をカバーする最小の範囲

難易度： hard

トピック：アレイ、ハッシュテーブル、貪欲、スライディングウィンドウ、ソート、ヒープ（優先キュー）

非廃止順序に並べ替えられた整数のkリストがあります。各kリストから少なくとも1つの数値を含む最小範囲を見つけます。

または a

例1：

• 入力： nums = [[4,10,15,24,26]、[0,9,12,20]、[5,18,22,30]] ]
• 出力： [20,24]
• 説明：
  リスト1：[4、10、15、24,26]、24は範囲です[20,24]。
  リスト2：[0、9、12、20]、20は範囲です[20,24]。
  リスト3：[5、18、22、30]、22は範囲です[20,24]。

例2：

• 入力： nums = [[1,2,3]、[1,2,3]、[1,2,3]]
• output： [1,1]

制約：

nums.length == k
1 1 -10
• 5 ⁵
nums [i]は
• don-decreasing order。でソートされます。

解決：

min-heap （または優先キュー）を使用して、各リストの最小要素を追跡しながら、各リストから少なくとも1つの要素を含む最小の範囲を見つけることができます。。

1. Min-Heap Initialization ：Min Heapを使用して、各要素を各Kリストから保存します。各ヒープエントリは、値、それが由来するリストのインデックス、およびそのリストの要素のインデックスを含むタプルになります。。
2. 最大値追跡：現在のウィンドウの最大値を追跡します。これは、範囲が最小の要素（ヒープから）と現在の最大値の違いによって決定されるため重要です。
リストの終了まで反復します
3. ：各反復について： ヒープから最小要素を抽出します。
   • 現在の範囲[min_value、max_value]が以前に記録された最小範囲よりも小さい場合、範囲を更新します。
   • 最小要素が取られたリストの次の要素に移動します。最大値を更新し、新しい要素をヒープに追加します。
終了
4. ：プロセスは、任意のリストが使い果たされると終了します。
このソリューションをphp：

Heap Initialization
1. ： 初期ヒープには、各リストの最初の要素が含まれています。また、最初の要素の中で最大要素を追跡します。
ヒープの処理
2. ： ヒープから最小要素を抽出し、同じリストから次の要素を追加して範囲を拡張しようとします（利用可能な場合）。
   。
   • 新しい要素をヒープに追加した後、新しい要素が大きい場合はmaxValueを更新します。
   • MaxValueとMinValueの差が以前に記録された範囲よりも小さいときはいつでも、最小の範囲を更新します。
   。
終了
3. ： ループは、すべてのリストを範囲内に含めることができなくなるため、リストが要素がなくなると停止します。
複雑さ分析

time complexity
• ：o（n * log k）。ここで、nはすべてのリストにわたって要素の総数、kはリストの数です。複雑さは、ヒープから要素を挿入して削除することから生じます。
スペースの複雑さ
• ：o（k）要素をヒープに保存するための
このソリューションは、各kソートされたリストから少なくとも1つの数値を含む最小の範囲を効率的に見つけます。

このシリーズが役立つと思う場合は、

をgithubでスターにするか、お気に入りのソーシャルネットワークの投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味があります！ このようなもっと役立つコンテンツが必要な場合は、私にフォローしてください：

linkedin
github