作者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/m.aspx?n=bbs/Marginalman/M.1730355432.A.58D.html