。坡道最大寬度

962。坡道最大寬度

難度：中

主題：陣列、堆疊、單調堆疊

整數陣列 nums 中的

ramp 是一對 (i, j)，其中 i j 且 nums[i] 寬度是j - i。

給定一個整數數組 nums，回傳 ramp 的最大寬度（以 nums 為單位）。如果 nums 中沒有 ramp，則傳回 0。

範例1：

• 輸入： nums = [6,0,8,2,1,5]
• 輸出： 4
• 解釋： 最大寬度斜坡在 (i, j) = (1, 5) 實現：nums[1] = 0 且 nums[5] = 5。

範例2：

• 輸入： nums = [9,8,1,0,1,9,4,0,4,1]
• 輸出： 7
• 解釋： 最大寬度斜坡在 (i, j) = (2, 9) 實現：nums[2] = 1 且 nums[9] = 1。

約束：

• 2 4
• 0 4

解：

我們可以利用單調堆疊的概念。解決方法及說明如下：

方法：

1. 單調遞減堆疊：我們建立一個堆疊，以 nums[stack[i]] 降序的方式追蹤元素的索引。這允許我們稍後找到 (i, j) 對，其中 nums[i]
2. 從末尾遍歷：建立堆疊後，我們從末尾（j從n-1到0）遍歷數組，嘗試找到每個j的最遠i，其中nums[i]
3. 更新最大寬度：每當 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. 時間複雜度:

   • 建置堆疊需要 O(n) 時間，因為每個索引都被推送一次。
   • 從末尾開始遍歷並彈出索引也需要 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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。坡道最大寬度的詳細內容。更多資訊請關注PHP中文網其他相關文章！