得到山形数组的最少删除次数(LeetCode日记)

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

题目信息:

我们定义 $arr$ 是 山形数组 当且仅当它满足：

• $arr.length>=3$
• 存在某个下标 $i$ （从 0 开始） 满足 $0<i<arr.length?1$ 且：
  • $arr[0]<arr[1]<...<arr[i?1]<arr[i]$
  • $arr[i]>arr[i+1]>...>arr[arr.length?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] ，是山形数组。

提示：

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• 题目保证 nums 删除一些元素后一定能得到山形数组。

相关标签 ：动态规划，二分查找

题解

这道题实际上是 Leetcode 第300题 最长递增子序列 的 扩展问题。建议大家在做这道题之前可以先去了解一下上面这道题的思路和代码。下面我们开始分析本题。

方法 ： 动态规划
根据题目的要求，我们需要使用最少的删除次数，使得给定的数组 $nums$ 成为 山形状数组。这等价于，我们需要找出数组 $nums$ 的一个最长的子序列，并且这个子序列是一个山形状数组。
因此，我们可以考虑枚举山形状数组的最高点。记数组 $nums$ 的长度为 $n$，并且枚举第 $i$ 个元素 $nums[i]$ 作为最高点，那么：

• $(1)$在数组的前缀部分 $nums[\mathrm{0..}i]$ ，找出一个严格递增的子序列，并且以 $nums[i]$结束，对应着山形状数组的上升部分；
• $(2)$在数组的后缀部分 $nums[i..n?1]$ ，找出一个严格递减的子序列，并且以 $nums[i]$开始，对应着山形状数组的下降部分。

由于我们需要找出最长的山形状数组，并且 $nums[\mathrm{0..}i]$ 和 $nums[i..n?1]$ 这两部分是互相独立的，那么我们只需要找出 $nums[\mathrm{0..}i]$ 中以 $nums[i]$ 结束的最长严格递增子序列，以及 $nums[i..n?1]$ 中以 $nums[i]$ 开始的最长严格递减子序列即可。

求解最长严格递增/递减子序列是一个非常经典的问题，即我们上文提到的 Leetcode 第300题 最长递增子序列 问题，使用动态规划或贪心算法的方法，可以在 $O(n^2)$ 或者 $O(nlog?n)$ 的时间内求出给定数组中，以每一个元素结尾的最长严格递增子序列的长度。
最长递增子序列问题的动态规划解法的状态转移方程如下，如果有需要的话，我可以在下一篇更新该问题。
$$dp[i]=\underset{0\le j<i,nums[j]<nums[i]}{\max }dp[j]+1$$

对于严格递减子序列的部分，我们可以把数组 $nums$ 进行反转，这样就从求解后缀的最长严格递减子序列，变成求解前缀的最长严格递增子序列了。

记 $pre[i]$ 和 $suf[i]$ 分别表示上文 (1)、(2) 中找出的最长子序列的长度，只要 $pre[i]$和 $suf[i]$均大于 1，就可以拼接成一个以 $nums[i]$ 为最高点的山形状数组，长度为 $L=pre[i]+suf[i]?1$，需要的删除次数为 $n?L$。

下面给出的代码使用了 上文提到的 最长递增子序列 问题的代码， 并将其中的代码封装成函数 $getLISArray$，用于求解所有的 $pre[i]$ ，并枚举 $i$ 以得出最终的答案。

实现代码(Python)

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        pre = self.getLISArray(nums)
        suf = self.getLISArray(nums[::-1])[::-1]
        ans = 0

        for pre_i, suf_i in zip(pre, suf):
            if pre_i > 1 and suf_i > 1:
                ans = max(ans, pre_i + suf_i - 1)
        
        return len(nums) - ans

    def getLISArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return dp

复杂度分析：

• 时间复杂度：$O(n^2)$ ，其中 $n$ 是数组 $nums$ 的长度。
• 空间复杂度：$O(n)$。

题记：

---

• 研究生在读，我会尽量保持LeetCode每日一题的思路和代码输出。希望大家多多支持。
• 水平有限，希望各位大佬能够批评指正。您的教诲是我进步的船帆。
• 希望各位跟我一样的小白能跟我一起参与到做题和讨论中来。共同进步是我所能期盼的最高愿想。
• 您的点赞和关注是我坚持分享的动力泉源，希望能将这件简单平凡的事一直做下去。感谢大家。

---