。最大幅ランプ

962。最大幅ランプ

難易度: 中

トピック: 配列、スタック、単調スタック

整数配列 nums 内の ramp は、i 幅は j - i です。

整数配列 nums を指定すると、ランプの最大幅を nums で返します。 nums に ramp がない場合は、0 を返します。

例 1:

• 入力: 数値 = [6,0,8,2,1,5]
• 出力: 4
• 説明: 最大幅ランプは、(i, j) = (1, 5): nums[1] = 0 および nums[5] = 5 で達成されます。

例 2:

• 入力: 数値 = [9,8,1,0,1,9,4,0,4,1]
• 出力: 7
• 説明: 最大幅ランプは、(i, j) = (2, 9): nums[2] = 1 および nums[9] = 1 で達成されます。

制約:

• 2 5 * 104
• ^{0 4}

解決策:

単調スタック

1. 単調減少スタック
: nums[stack[i]] が降順になるように要素のインデックスを追跡するスタックを作成します。これにより、後で nums[i] 最後からのトラバース: スタックを作成した後、配列を最後 (n-1 から 0 までの j) からトラバースして、各 j の最も遠い i を見つけます (ここで、nums[i] 最大幅を更新します: スタックの現在のトップに nums[i]

このソリューションを PHP で実装してみましょう: 962。最大幅ランプ


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

// Example 1
$nums = [6, 0, 8, 2, 1, 5];
echo maxWidthRamp($nums);  // Output: 4

// Example 2
$nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1];
echo maxWidthRamp($nums);  // Output: 7
?>

ログイン後にコピー
説明：

1. 減少するスタックを作成します

   :
   配列を反復処理し、インデックスをスタックに追加します。
   スタック内の最後のインデックスの値以下の値に対応する場合にのみ、インデックスを追加します。これにより、スタック内の値が確実に降順になります。

2. 端からトラバース

   :
   配列を逆方向に遡って、各 j について、nums[i]
幅 j - i を計算し、maxWidth を更新します。

3. これが機能する理由

   :
   インデックスの減少するスタックを維持することにより、より大きな値を持つ j に遭遇したときに、i がスタックからポップされるときに、より大きな幅 j - i が得られることが保証されます。

4. 時間計算量

   :
   各インデックスが 1 回プッシュされるため、スタックの構築には O(n) 時間がかかります。
   各インデックスは最大 1 回ポップされるため、終端からの走査とインデックスのポップにも O(n) かかります。
   全体として、ソリューションは O(n) 時間で実行され、最大 5 * 10^4 の入力サイズに対して効率的です。
出力：

nums = [6, 0, 8, 2, 1, 5] の場合、出力は 4 で、ランプ (1, 5) に対応します。
nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1] の場合、出力は 7 で、ランプ (2, 9) に対応します。

連絡先リンク

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

• LinkedIn
• GitHub

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