跳至主要內容

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


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

🔴   🔖  贪心 数组 二分查找 动态规划  🔗 力扣open in new window LeetCodeopen in new window

题目

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] > 1LDS[i] > 1,并更新最大山脉长度。
  5. 返回最小删除次数

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

复杂度分析

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

代码

/**
 * @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最长递增子序列[✓]数组 二分查找 动态规划🟠🀄️open in new window 🔗open in new window
845数组中的最长山脉[✓]数组 双指针 动态规划 1+🟠🀄️open in new window 🔗open in new window
852山脉数组的峰顶索引[✓]数组 二分查找🟠🀄️open in new window 🔗open in new window
941有效的山脉数组数组🟢🀄️open in new window 🔗open in new window
1095山脉数组中查找目标值数组 二分查找 交互🔴🀄️open in new window 🔗open in new window
2865美丽塔 I 数组 单调栈🟠🀄️open in new window 🔗open in new window
2866美丽塔 II 数组 单调栈🟠🀄️open in new window 🔗open in new window