【算法】【Python3、动态规划、贪心、二分查找】力扣1671. 得到山形数组的最少删除次数-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】【Python3、动态规划、贪心、二分查找】力扣1671. 得到山形数组的最少删除次数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1671. 得到山形数组的最少删除次数

【算法】【动态规划、贪心、二分查找】力扣1671. 得到山形数组的最少删除次数

问题描述

给定一个整数数组 nums ，我们定义该数组为山形数组当且仅当：

nums 的长度至少为 3。
存在一个下标 i 满足 0 < i < len(nums) - 1 且：
- nums[0] < nums[1] < ... < nums[i - 1] < nums[i]
- nums[i] > nums[i + 1] > ... > nums[len(nums) - 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]。

解法一：动态规划

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        # suf[i] 为以i为起点的后缀最长严格下降子序列的长度
        suf = [1] * n
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if nums[j] < nums[i]:
                    suf[i] = max(suf[i], suf[j] + 1)
        
        mx = 0
        pre = [1] * n
        for i in range(0, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    pre[i] = max(pre[i], pre[j] + 1)
            if pre[i] >= 2 and suf[i] >= 2:
                mx = max(mx, pre[i] + suf[i] - 1)
        return n - mx

解法分析：

构建两个数组 pre 和 suf，分别表示以每个元素为起点的最长上升和下降子序列的长度。
使用两层嵌套循环更新 pre 和 suf 数组。
寻找满足条件的元素，计算最大山形数组长度，最终返回删除元素的个数。

复杂度分析：

时间复杂度： $O(n^2)$
空间复杂度： $O (n)$

解法二：贪心 + 二分

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        suf = [0] * n
        g = []  # g[i] 代表最长上升子序列长度为 i + 1 的最小元素
        for i in range(n - 1, 0, -1):
            x = nums[i]
            j = bisect_left(g, x)  # 寻找第一个 >= x 的元素的下标
            if j == len(g):  # 代表没有 >= x 的元素
                g.append(x)  # 添加 x 到 g
            else:
                g[j] = x  # 更新最小元素
            suf[i] = j + 1  # j + 1 代表了这个序列的长度。

        mx = 0
        g = []
        pre = 0
        for i in range(0, n, 1):
            x = nums[i]
            j = bisect_left(g, x)
            if j == len(g):
                g.append(x)
            else:
                g[j] = x
            pre = j + 1
            # 题目要求数组长度至少为3，
            # 也就是说，最简单的山形数组的最大值在正中间，左右至少有一个元素
            # 能组成山形数组的子序列也要满足这个要求
            # pre == 1代表左边没有元素，suf[i] == 1代表右边没有元素。
            if pre >= 2 and suf[i] >= 2:
                mx = max(mx, pre + suf[i] - 1)
        return len(nums) - mx

解法分析：

利用贪心思想，维护一个辅助数组 g，其中 g[i] 代表最长上升子序列长度为 i + 1 的最小元素。
使用二分查找更新 g 数组。
遍历数组，计算最大山形数组长度，最终返回删除元素的个数。

复杂度分析：

时间复杂度： $O (n l o g n)$
空间复杂度： $O (n)$

总结

本文介绍了解决力扣1671题的两种方法：动态规划和贪心 + 二分。动态规划方法通过构建两个辅助数组，分别表示以每个元素为起点的最长上升和下降子序列的长度，然后遍历数组寻找满足条件的元素，计算最大山形数组长度。贪心 + 二分方法则利用贪心思想和二分查找，维护一个辅助数组，遍历数组计算最大山形数组长度。两种方法的时间复杂度分别为 O(n^2) 和 O(n log n)，空间复杂度均为 O(n)。在实际应用中，可以根据具体情况选择适合的方法。文章来源地址https://www.toymoban.com/news/detail-800287.html

到了这里，关于【算法】【Python3、动态规划、贪心、二分查找】力扣1671. 得到山形数组的最少删除次数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！