1671. 得到山形数组的最少删除次数

🔴   🔖  贪心 数组 二分查找 动态规划  🔗 力扣 LeetCode

题目

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums​​​, return the minimum number of elements to remove to make nums a mountain array.

Example 1:

Input: nums = [1,3,1]

Output: 0

Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

Input: nums = [2,1,1,5,6,2,3,1]

Output: 3

Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Constraints:

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 10^9
• It is guaranteed that you can make a mountain array out of nums.

题目大意

我们定义 arr 是 山形数组 当且仅当它满足：

• arr.length >= 3
• 存在某个下标 i （从 0 开始 ） 满足 0 < i < arr.length - 1 且：
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • 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 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。

提示：

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 10^9
• 题目保证 nums 删除一些元素后一定能得到山形数组。

解题思路

这道题要求我们找出将一个数组转换为山脉数组所需的最小删除次数，一个山脉数组的定义是：数组必须先严格递增然后严格递减。因此，可以讲题目转化为求山脉数组的最大长度，可以利用动态规划来解决这个问题，具体步骤如下：

1. 定义两个动态规划数组：

   • LIS[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
   • LDS[i] 表示以 nums[i] 开头的最长递减子序列的长度。

2. 从左到右计算 LIS：

   • 遍历数组，对于每个元素 nums[i]，更新其 LIS 值。
   • LIS[i] 是 1 + max(LIS[j])，其中 j 是所有满足 nums[j] < nums[i] 的索引。

3. 从右到左计算 LDS：

   • 遍历数组的逆序，对于每个元素 nums[i]，更新其 LDS 值。
   • LDS[i] 是 1 + max(LDS[j])，其中 j 是所有满足 nums[j] < nums[i] 的索引。

4. 计算最大山脉长度：

   • 遍历每个元素，检查 LIS[i] > 1 和 LDS[i] > 1，并更新最大山脉长度。

5. 返回最小删除次数：

   • 最小删除次数等于数组的长度减去最大山脉数组的长度，即 n - maxMountain。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组的长度，由于计算 LIS 和 LDS 时的双重循环。在实际应用中，对于更大的输入，利用其他优化方法，比如二分搜索，可以将复杂度进一步降低至 O(n log n)。
• 空间复杂度：O(n)，存储 LIS 和 LDS 需要线性空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumMountainRemovals = function (nums) {
	const n = nums.length;
	// 需要至少三个元素才能形成山脉
	if (n < 3) return 0;

	let LIS = new Array(n).fill(1),
		LDS = new Array(n).fill(1);

	// 计算 LIS
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < i; j++) {
			if (nums[i] > nums[j]) {
				LIS[i] = Math.max(LIS[i], LIS[j] + 1);
			}
		}
	}

	// 计算 LDS
	for (let i = n - 1; i > 0; i--) {
		for (let j = n - 1; j > i; j--) {
			if (nums[i] > nums[j]) {
				LDS[i] = Math.max(LDS[i], LDS[j] + 1);
			}
		}
	}

	let maxMountain = 0;

	// 计算最大山脉长度
	for (let i = 0; i < n; i++) {
		if (LIS[i] > 1 && LDS[i] > 1) {
			maxMountain = Math.max(maxMountain, LIS[i] + LDS[i] - 1);
		}
	}
	// 返回最小删除次数
	return n - maxMountain;
};

相关题目

题号	标题	题解	标签	难度
300	最长递增子序列	[✓]	数组 二分查找 动态规划
845	数组中的最长山脉	[✓]	数组 双指针 动态规划 1+
852	山脉数组的峰顶索引	[✓]	数组 二分查找
941	有效的山脉数组		数组
1095	山脉数组中查找目标值		数组 二分查找 交互
2865	美丽塔 I		栈 数组 单调栈
2866	美丽塔 II		栈 数组 单调栈