作者DJYOMIYAHINA (通通打死)
看板Marginalman
标题Re: [闲聊] 每日leetcode
时间Thu Oct 31 15:19:14 2024
不知道哪一天的
看hint 我连LIS都不知道==
查了才知道
用了最简单的N^2方法
能过就好
def minimumMountainRemovals(self, nums: List[int]) -> int:
n = len(nums)
dp_lr = [1 for _ in range(n)]
dp_rl = [1 for _ in range(n)]
for i in range(n):
for j in range(i):
if nums[j]<nums[i]:
dp_lr[i] = max(dp_lr[i], dp_lr[j]+1)
for i in reversed(range(n)):
for j in range(n-1, i, -1):
if nums[j]<nums[i]:
dp_rl[i] = max(dp_rl[i], dp_rl[j]+1)
ans = n
for i in range(n):
if dp_rl[i]>1 and dp_lr[i]>1:
ans = min(ans, n-(dp_rl[i]+dp_lr[i]-1))
return ans
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 125.228.146.144 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Marginalman/M.1730359156.A.035.html