制作山脉阵列的最少移除次数

1671。制作山阵的最少移除次数

难度：难

主题：数组、二分查找、动态规划、贪心

你可能还记得，数组 arr 是一个 山数组 当且仅当：

• arr.length >= 3
• 存在一些索引 i (0-indexed)，其中 0
  我
arr[0] arr[i]> arr[i 1] > ...>> arr[arr.length - 1]

给定一个整数数组 nums，返回要删除的最小个元素，以使 nums 成为山数组

。

示例1：

• 输入：
nums = [1,3,1]
• 输出：
0
• 说明：
数组本身就是一个山数组，所以我们不需要删除任何元素。

示例2：

• 输入：
nums = [2,1,1,5,6,2,3,1]
• 输出：
3
• 解释：
一种解决方案是删除索引 0、1 和 5 处的元素，使数组 nums = [1,5,6,3,1]。

约束：

3 1 9
保证你可以用nums制作一个山形数组。

提示：

考虑相反的方向而不是最小元素来删除最大山子序列
想想 LIS，它有点接近

解决方案：

我们可以使用动态规划方法，其思想是找到最大山子序列，而不是直接计算要删除的元素。这种方法基于为数组中的每个位置找到两个最长递增子序列（LIS）：一个为从左到右，另一个为从右到-离开

。一旦我们有了尽可能长的山子序列，原始数组长度和该子序列长度之间的差异将为我们提供要删除的最少元素。

解决方案概要

1. 识别增加的子序列长度

   :
   计算 leftLIS 数组，其中 leftLIS[i] 表示以 i 结尾的最长递增子序列的长度（从左到右）。

2. 识别递减的子序列长度

   :
   • 计算rightLIS数组，其中rightLIS[i]表示从i开始（从右到左）的最长递减子序列的长度。

3. 计算最大山长:

   • 对于每个索引 i，其中 0 1 且 rightLIS[i] > 1）。计算 i 处的山长为 leftLIS[i] rightLIS[i] - 1.

4. 获得最小移除量：

   • 要删除的最小元素将是原始数组长度减去找到的最长山的长度。

让我们用 PHP 实现这个解决方案：1671。制作山脉阵列的最少移除次数

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

// Example usage
$nums1 = [1, 3, 1];
echo minimumMountainRemovals($nums1); // Output: 0

$nums2 = [2, 1, 1, 5, 6, 2, 3, 1];
echo minimumMountainRemovals($nums2); // Output: 3
?>

解释：

1. 左LIS计算:

   • leftLIS[i] 存储以 i 结尾的递增子序列的最大长度。我们迭代每个 i，对于每个 i，从 0 迭代到 i-1，找到以 i 结尾的最长子序列。

2. 正确的 LIS 计算:

   • rightLIS[i] 存储从 i 开始的递减子序列的最大长度。我们从 n-2 向后迭代到 0，对于每个 i，从 n-1 向下迭代到 i 1 以找到从 i 开始的最长子序列。

3. 山脉计算:

   • 索引 i 处的有效峰值必须具有 leftLIS[i] > 1 且右LIS[i]> 1. 峰位于 i 的山的长度为 leftLIS[i] rightLIS[i] - 1.

4. 最终计算：

   • 所需的最小移除量是原始数组长度与找到的最大山体长度之间的差值。

复杂性分析

• 时间复杂度：O(n²)，由于LIS计算中的双循环。
• 空间复杂度：O(n)，用于存储leftLIS和rightLIS数组。

该解决方案确保我们找到最大的山脉子序列并计算实现山脉阵列所需的最小移除量。

联系链接

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

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

• 领英
• GitHub

以上是制作山脉阵列的最少移除次数的详细内容。更多信息请关注PHP中文网其他相关文章！