。坡道最大宽度

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中文网其他相关文章！