。配列内の最大距離

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 == arrays.length
• 2 5
• 1
• -10⁴ <= 配列[i][j] <= 10⁴
• arrays[i] は 昇順 でソートされます。
• すべての配列には最大 10⁵ の整数が存在します。

解決策:

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

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

1. 配列を反復処理しながら最小値と最大値を追跡します。
2. 各配列について、現在の配列の最小値とグローバル最大値、および現在の配列の最大値とグローバル最小値を比較することにより、潜在的な最大距離を計算します。
3. 作業を進めながら、グローバル最小値と最大値を更新します。

このソリューションを PHP で実装してみましょう: 624。配列内の最大距離

  
  
  説明：




min_value と max_value は、最初の配列の最小値と最大値で初期化されます。
2 番目の配列から始めて各配列を反復処理すると、次のようになります。


グローバル最小値と現在の配列の最大値、およびグローバル最大値と現在の配列の最小値を比較して距離を計算します。
より大きな距離が見つかった場合は常に max_ distance を更新します。
これまでに検出された最小値と最大値を反映するように min_value と max_value を更新します。





最後に、この関数は見つかった最大距離を返します。



このソリューションは O(m) 時間で実行されます (m は配列の数)。問題の制約を考慮すると効率的です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

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


LinkedIn
GitHub



          

            
  

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