作者JIWP (神楽めあ的钱包)
看板Marginalman
标题Re: [闲聊] 每日leetcode
时间Thu Oct 31 14:17:09 2024
1671. Minimum Number of Removals to Make Mountain Array
一个array可以称做是mountain array如果满足下列条件
(1) arr.length >= 3
(2) arr[0] < arr[1] < ... < arr[i-1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
给一个array : nums
请回传最少从nums移除掉几个元素，可以使nums变成mountain array
思路 :
最少移除多少元素 = 变成mountain array後最长的nums
假设nums[i]是mountain array的顶峰
这样nums[i]的右边会是严格递减、左边会是严格递增
假设nums的长度为n
就从nums[0]和nums[n-1]开始跑一次longest increasing subsequence
并分别用dp1、dp2纪录subsequence的长度
dp1[i]+dp2[i]-1就会是顶峰为nums[i]的mountain array的长度
去找出最长的长度max_length
最後回传n-max_length就可以
最後要记得mountain array不可以是一个单纯递增或递减的array
所以dp1[i]、dp2[i]都不可以等於1
golang code :
func minimumMountainRemovals(nums []int) int {
n, max_remain := len(nums), 0
lis1, lis2 := make([]int, n), make([]int, n)
dp1, dp2 := []int{nums[0]}, []int{nums[n-1]}
lis1[0], lis2[n-1] = 1, 1
for i := 1; i < n; i++ {
idx1, idx2 := sort.SearchInts(dp1, nums[i]), sort.SearchInts(dp2, nums[n-1-i
])
if idx1 == len(dp1) {
dp1 = append(dp1, nums[i])
} else {
dp1[idx1] = nums[i]
}
if idx2 == len(dp2) {
dp2 = append(dp2, nums[n-1-i])
} else {
dp2[idx2] = nums[n-1-i]
}
lis1[i] = idx1 + 1
lis2[n-1-i] = idx2 + 1
}
for i := 0; i < n; i++ {
if lis1[i] != 1 && lis2[i] != 1 {
max_remain = max(max_remain, lis1[i]+lis2[i]-1)
}
}
return n - max_remain
}
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.71.213.179 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Marginalman/M.1730355432.A.58D.html