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

Question

我们定义 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 = [4,3,2,1,1,2,3,1]
输出：4
提示：

输入：nums = [1,2,3,4,4,3,2,1]
输出：1

提示：

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

前置知识

• 最长上升子序列

思路

看了下数据范围 3 <= nums.length <= 1000。直接莽过没问题。

这道题需要你有最长上升子序列的知识。

有了这样的一个知识前提，我们可以枚举所有的山顶。那么

• 左侧需要删除的个数其实就是 L - LIS_LEFT，其中 L 为左侧长度，LIS_LEFT 为左侧的最长上升子序列长度。
• 右侧需要删除的个数其实就是 R - LDS_RIGHT，其中 R 为右侧长度，LDS_RIGHT 为右侧的最长下降子序列长度。

为了将逻辑统一为 最长上升子序列长度，我们可以将 R 翻转一次。

枚举山顶的时间复杂度为 $O(N)$，常规的 LIS 复杂度为 $O(N^2)$。

根据时间复杂度速查表：

时间复杂度速查表可以在我的刷题插件中查到。刷题插件可以在我的公众号《力扣加加》回复插件获取。

本题的数据范围为 <= 1000。因此 $N^3$ 无法通过。不过我们可以使用贪心求 LIS，时间复杂度为 $N^2logN$，勉强可以通过。关于贪心求解 LIS，上面的文章也有提到。

代码

代码支持：Python3

Python3 Code:

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        ans = n
        def LIS(A):
            d = []
            for a in A:
                i = bisect.bisect_left(d, a)
                if i < len(d):
                    d[i] = a
                elif not d or d[-1] < a:
                    d.append(a)
            return d.index(A[-1])

        for i in range(1, n-1):
            l, r = LIS(nums[:i+1]), LIS(nums[i:][::-1])
            if not l or not r: continue
            ans = min(ans, n - 1 - l - r)
        return ans

复杂度分析

令 N 为数组长度。

• 时间复杂度：$O(N^2logN)$
• 空间复杂度：$O(N)$