1671. 得到山形数组的最少删除次数
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) with0 < 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
删除一些元素后一定能得到山形数组。
解题思路
这道题要求我们找出将一个数组转换为山脉数组所需的最小删除次数,一个山脉数组的定义是:数组必须先严格递增然后严格递减。因此,可以讲题目转化为求山脉数组的最大长度,可以利用动态规划来解决这个问题,具体步骤如下:
定义两个动态规划数组:
LIS[i]
表示以nums[i]
结尾的最长递增子序列的长度。LDS[i]
表示以nums[i]
开头的最长递减子序列的长度。
从左到右计算 LIS:
- 遍历数组,对于每个元素
nums[i]
,更新其LIS
值。 LIS[i]
是1 + max(LIS[j])
,其中j
是所有满足nums[j] < nums[i]
的索引。
- 遍历数组,对于每个元素
从右到左计算 LDS:
- 遍历数组的逆序,对于每个元素
nums[i]
,更新其LDS
值。 LDS[i]
是1 + max(LDS[j])
,其中j
是所有满足nums[j] < nums[i]
的索引。
- 遍历数组的逆序,对于每个元素
计算最大山脉长度:
- 遍历每个元素,检查
LIS[i] > 1
和LDS[i] > 1
,并更新最大山脉长度。
- 遍历每个元素,检查
返回最小删除次数:
- 最小删除次数等于数组的长度减去最大山脉数组的长度,即
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 | 栈 数组 单调栈 | 🟠 | 🀄️ 🔗 |