。配列内の最大距離

624。配列内の最大距離

難易度:中

トピック:配列、貪欲

m 個の配列が与えられ、各配列は昇順でソートされます。

2 つの異なる配列から 2 つの整数を取得し (各配列が 1 つを選択します)、距離を計算できます。 2 つの整数 a と b の間の距離を、それらの絶対差 |a - b| として定義します。

最大距離を

返します

例1:

入力:
• 配列 = [[1,2,3],[4,5],[1,2,3]]
出力:
• 4
説明:
• 最大距離 4 に到達する 1 つの方法は、最初または 3 番目の配列で 1 を選択し、2 番目の配列で 5 を選択することです。

例 2:

入力:
• 配列 = [[1],[1]]
出力:
• 0

制約:

m == 配列.長さ

• 2 5
• 1
• -10
4
• <= 配列[i][j] <= 10⁴arrays[i] は
昇順
• でソートされます。すべての配列には最大 105
の整数が含まれます。
解決策:

それぞれ異なる配列から選択された 2 つの整数の間の可能な最大距離を計算する必要があります。重要な観察は、最大距離は、ある配列の最小値と別の配列の最大値の間にある可能性が高いということです。

この問題を解決するには、次の手順に従います:

配列を反復処理しながら最小値と最大値を追跡します。

各配列について、現在の配列の最小値とグローバル最大値、および現在の配列の最大値とグローバル最小値を比較することにより、潜在的な最大距離を計算します。
作業を進めながら、グローバル最小値と最大値を更新します。
3. このソリューションを PHP で実装しましょう:
624。配列内の最大距離

リーリー説明：

min_value

と
• max_valueは、最初の配列の最小値と最大値で初期化されます。2 番目の配列から始めて各配列を反復処理すると、次のようになります。
グローバル最小値と現在の配列の最大値、およびグローバル最大値と現在の配列の最小値を比較することによって距離を計算します。
• より大きな距離が見つかった場合は常に max_ distance を更新します。
  これまでに発生した最小値と最大値を反映するように min_value と max_value を更新します。
  最後に、関数は見つかった最大距離を返します。
• このソリューションは O(m) 時間で実行されます。ここで、m は配列の数であり、問題の制約を考慮すると効率的です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub でリポジトリ

にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとってとても意味のあるものになります！

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

リンクトイン

• GitHub

以上が。配列内の最大距離の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。