🏃♂️ Jump Game II アルゴリズム詳細解析
⚡ アルゴリズムの計算量
時間計算量: O(n) - 配列を一度だけスキャン
空間計算量: O(1) - 定数の追加メモリのみ使用
🔄 アルゴリズムの流れ
2
現在のジャンプ範囲の終端に到達したらジャンプ実行
📊 Example 1: nums = [2,3,1,1,4]
🎮 インタラクティブデモ
jumps = 0
currentEnd = 0
farthest = 0
開始状態: インデックス0からスタート
📊 Example 2: nums = [2,3,0,1,4]
🎮 インタラクティブデモ
jumps = 0
currentEnd = 0
farthest = 0
開始状態: インデックス0からスタート
🧠 アルゴリズムの核心理念
グリーディアプローチ:
各段階で最も遠くまで到達できる選択肢を保持し、必要な時点で最適なジャンプを実行します。
重要なポイント:
farthest: 現在までに発見した到達可能な最遠距離currentEnd: 現在のジャンプで到達できる範囲の終端currentEndに到達した時点で、必ずジャンプが必要- 次のジャンプの到達範囲は
farthestで決定
// 核心ロジック
for (let i = 0; i < n - 1; i++) {
// 現在位置から到達可能な最遠距離を更新
farthest = Math.max(farthest, i + nums[i]);
// 現在のジャンプ範囲の終端に到達
if (i === currentEnd) { jumps++;
// ジャンプ実行 currentEnd = farthest;
// 次の範囲設定
if (currentEnd >= n - 1) break; } }