Skip to content

Latest commit

 

History

History
174 lines (130 loc) · 7.14 KB

1671.md

File metadata and controls

174 lines (130 loc) · 7.14 KB
title description keywords
1671. 得到山形数组的最少删除次数
LeetCode 1671. 得到山形数组的最少删除次数题解，Minimum Number of Removals to Make Mountain Array，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
1671. 得到山形数组的最少删除次数
得到山形数组的最少删除次数
Minimum Number of Removals to Make Mountain Array
解题思路
贪心
数组
二分查找
动态规划

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

🔴 Hard  🔖  贪心 数组 二分查找 动态规划  🔗 力扣 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 栈 数组 单调栈 🟠 🀄️ 🔗