連続サブアレイ

2762。連続部分配列

難易度: 中

トピック: スライディング ウィンドウ、配列、順序付きセット、ヒープ (優先キュー)、キュー、モノトニック キュー、2 ポインター、順序付きマップ、ハッシュ テーブル、動的プログラミング、カウンティング、数学、二分探索ツリー、セグメントツリー、ツリー、スタック、二分探索、単調スタック、メモ化、イテレータ、貪欲、深さ優先検索、再帰

0 からインデックス付けされた 整数配列 nums が与えられます。次の場合、nums の部分配列は連続と呼ばれます。

• i、i 1、...、j を部分配列のインデックスとします。次に、インデックスの各ペアについて、 i ₁, i₂ 1] - nums[i₂]|

連続する部分配列の合計数を返します。

サブ配列は、配列内の要素の連続した 空でない シーケンスです。

例 1:

• 入力: 数値 = [5,4,2,4]
• 出力: 8
• 説明:
  • サイズ 1 の連続部分配列: [5]、[4]、[2]、[4]。
  • サイズ 2 の連続部分配列: [5,4]、[4,2]、[2,4]。
  • サイズ 3 の連続部分配列: [4,2,4]。
  • サイズ 4 のサブアレイはありません。
  • 連続部分配列の合計 = 4 3 1 = 8。
  • これ以上連続する部分配列が存在しないことがわかります。

例 2:

• 入力: 数値 = [1,2,3]
• 出力: 6
• 説明:
  • サイズ 1 の連続部分配列: [1]、[2]、[3]。
  • サイズ 2 の連続部分配列: [1,2]、[2,3]。
  • サイズ 3 の連続部分配列: [1,2,3]。
  • 連続部分配列の合計 = 3 2 1 = 6。

制約:

• 1 5
• 1 9

ヒント:

1. スライディング ウィンドウ手法を使用してみてください。
2. セットまたはマップを使用して、部分配列の最大値と最小値を追跡します。

解決策:

スライディング ウィンドウ手法を使用して、連続部分配列の数を効率的に計算できます。部分配列内の最大値と最小値の差が最大 2 である有効なウィンドウを維持します。現在のウィンドウ内の最大値と最小値を効率的に追跡するには、2 つの デキュー (1 つは1 つは最大値、1 つは最小値です)。

アプローチ

1. 左と右の 2 つのポインターを使用してスライディング ウィンドウ手法を使用します。
2. 2 つの deques を使用します。
   • 最大値の降順で要素のインデックスを追跡するもの。
   • 要素のインデックスを最小値の昇順で追跡するもの。
3. 各インデックス右について:
   • 現在のウィンドウを反映するように両端キューを更新します。
   • ウィンドウが有効なままであることを確認します (最大値と最小値の差 ≤ 2)。無効な場合は、左ポインタを増分してウィンドウを縮小します。
   • インデックス右で終わる有効な部分配列の数を (右 - 左 1) として数えます。
4. 部分配列の総数を返します。

このソリューションを PHP で実装してみましょう: 2762。連続部分配列

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function continuousSubarrays($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$nums1 = [5, 4, 2, 4];
echo continuousSubarrays($nums1) . "\n"; // Output: 8

$nums2 = [1, 2, 3];
echo continuousSubarrays($nums2) . "\n"; // Output: 6
?>

説明：

1. スライディング ウィンドウ:
   
   左ポインタは、ウィンドウが無効になった場合（つまり、最大値と最小値の差が 2 を超えた場合）にのみ前に移動します。右ポインタは、配列を反復処理してウィンドウを拡張します。

2. 最大値と最小値のデック:

   • maxDeque は常に要素のインデックスを降順で保持し、現在のウィンドウの最大値が先頭 (maxDeque[0]) になるようにします。
   • minDeque は常に要素のインデックスを昇順で保持し、現在のウィンドウの最小値が先頭 (minDeque[0]) になるようにします。

3. サブ配列のカウント:
   
   左から右へのすべてのサブ配列が有効であるため、右ごとに、右で終わる有効なサブ配列の数は (右 - 左 1) に等しくなります。

4. 効率:
   
   各要素は両端キューに追加および削除されるのは最大 1 回であるため、時間計算量は O(n) になります。デキューのため、スペースの複雑さは O(n) です。

---

出力

8
6

---

複雑さの分析

1. 時間計算量:

   • 各要素は、両端キューから最大 1 回プッシュおよびポップされます。
   • 合計時間計算量は O(n) です。

2. 空間の複雑さ:

   • 最大サイズ n のインデックスを格納します。
   • 空間の複雑さは O(n) です。

この実装は効率的であり、指定された制約内で動作します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が連続サブアレイの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。