前言
持续更新了
正文
问题来源
本问题来自leetcode上的1671题。
问题描述
我们定义 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 = [4,3,2,1,1,2,3,1]
输出：4
示例 4:
输入：nums = [1,2,3,4,4,3,2,1]
输出：1
分析：
问题转化为 左右上升子序列的最长长度
func max(a, b int) int {
if a > b {
return a
}
return b
}
func minimumMountainRemovals(nums []int) int {
ldp := make([]int, len(nums))
rdp := make([]int, len(nums))
ldp[0] = 1
rdp[len(nums)-1] = 1
for i := 1; i < len(nums); i++ {
ldp[i] = 1
for j := 0; j < i; j++ {
if nums[i] > nums[j] {
ldp[i] = max(ldp[i], ldp[j]+1)
}
}
}
for i := len(nums)-2; i >=0; i-- {
rdp[i] = 1
for j := len(nums)-1; j > i; j-- {
if nums[i] > nums[j] {
rdp[i] = max(rdp[i], rdp[j]+1)
}
}
}
m := 0
for i := 0; i < len(nums); i++ {
if ldp[i] > 1 && rdp[i] > 1 {
m = max(m, ldp[i]+rdp[i]-1)
}
}
return len(nums) - m
}
总结：
勤思考。
结语
不管怎么样好好加油。
