Day68力扣打卡

2023-12-22 21:41:53

打卡记录

在这里插入图片描述


得到山形数组的最少删除次数（线性DP + 前后缀分解）

链接

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        pre, suf = [1] * n, [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    pre[i] = max(pre[i], pre[j] + 1)
                if nums[n - 1 - i] > nums[n - 1 - j]:
                    suf[n - 1 - i] = max(suf[n - 1 - i], suf[n - 1 - j] + 1)
        return min(n - (pre[i] + suf[i] - 1) for i in range(n) if pre[i] != 1 and suf[i] != 1)

文章来源:https://blog.csdn.net/qq947467490/article/details/135147100
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。