要删除以使数组排序的最短子数组

1574。删除最短子数组以使数组排序

难度：中等

主题：数组、两个指针、二分查找、堆栈、单调堆栈

给定一个整数数组 arr，从 arr 中删除一个子数组（可以为空），使得 arr 中的剩余元素非递减。

返回要删除的最短子数组的长度.

子数组是数组的连续子序列。

示例1：

• 输入： arr = [1,2,3,10,4,2,3,5]
• 输出： 3
• 解释： 我们可以删除的最短子数组是长度为 3 的 [10,4,2]。之后的剩余元素将是已排序的 [1,2,3,3,5]。
  • 另一个正确的解决方案是删除子数组 [3,10,4]。

示例2：

• 输入： arr = [5,4,3,2,1]
• 输出： 4
• 解释：由于数组是严格递减的，所以我们只能保留单个元素。因此我们需要删除长度为 4 的子数组，可以是 [5,4,3,2] 或 [4,3,2,1]。

示例 3：

• 输入： arr = [1,2,3]
• 输出： 0
• 解释： 数组已经是非递减的。我们不需要删除任何元素。

约束：

• 1 5
• 0 9

提示：

1. 关键是找到分别从第一个元素开始或以最后一个元素结束的最长非递减子数组。
2. 删除一些子数组后，结果是排序后的前缀和排序后缀的串联，其中前缀的最后一个元素小于后缀的第一个元素。

解决方案：

我们可以使用排序和二分搜索技术。计划如下：

方法：

1. 双指针方法：

   • 首先，确定最长的非递减前缀（左指针）。
   • 然后，找出最长的非递减后缀（右指针）。
   • 之后，尝试将这两个子数组组合起来，考虑数组的中间部分，并调整要删除的子数组，使组合后的数组不减。

2. 单调堆栈：

   • 使用单调堆栈来帮助以排序方式管理子数组元素。

3. 步骤：

   • 找到最长的非递减前缀（左）。
   • 找到最长的非递减后缀（右）。
   • 尝试通过寻找可以形成有效组合的元素来合并两个子数组。

4. 优化：

   • 使用二分搜索来优化合并步骤，以找到要删除的最小子数组。

让我们用 PHP 实现这个解决方案：1574。要删除以使数组排序的最短子数组

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

// Test cases
echo shortestSubarrayToRemove([1, 2, 3, 10, 4, 2, 3, 5]) . "\n"; // Output: 3
echo shortestSubarrayToRemove([5, 4, 3, 2, 1]) . "\n";           // Output: 4
echo shortestSubarrayToRemove([1, 2, 3]) . "\n";                 // Output: 0
?>

解释：

1. 最长非递减前缀和后缀:

   • 前缀是通过从头开始遍历数组直到元素按非递减顺序确定的。
   • 同理，后缀也是从尾部开始遍历确定的。

2. 初始最小移除：

   • 仅保留前缀或后缀来计算移除长度。

3. 合并前缀和后缀:

   • 使用两个指针（i 表示前缀，j 表示后缀）找到要删除的最小子数组，使得前缀的最后一个元素小于或等于后缀的第一个元素。

4. 返回结果:

   • 结果是要删除的子数组的最小长度，计算为初始删除或前缀和后缀合并中较小的一个。

复杂

• 时间复杂度：O(n)，因为数组最多遍历两次。
• 空间复杂度：O(1)，因为只使用了几个变量。

该解决方案可以有效地找到要删除的最短子数组，从而使用两指针技术对数组进行排序，并且可以处理最多 10^5 个元素的约束的大型数组。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是要删除以使数组排序的最短子数组的详细内容。更多信息请关注PHP中文网其他相关文章！