第六章 - 高频考题(困难)
1671. 得到山形数组的最少删除次数

题目地址(1671. 得到山形数组的最少删除次数)

题目描述

1
我们定义 arr 是 山形数组 当且仅当它满足:
2
3
arr.length >= 3
4
存在某个下标 i (从 0 开始) 满足 0 < i < arr.length - 1 且:
5
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
6
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
7
给你整数数组 nums​ ,请你返回将 nums 变成 山形状数组 的​ 最少 删除次数。
8
9
10
11
示例 1:
12
13
输入:nums = [1,3,1]
14
输出:0
15
解释:数组本身就是山形数组,所以我们不需要删除任何元素。
16
示例 2:
17
18
输入:nums = [2,1,1,5,6,2,3,1]
19
输出:3
20
解释:一种方法是将下标为 0,1 和 5 的元素删除,剩余元素为 [1,5,6,3,1] ,是山形数组。
21
示例 3:
22
23
输入:nums = [4,3,2,1,1,2,3,1]
24
输出:4
25
提示:
26
27
输入:nums = [1,2,3,4,4,3,2,1]
28
输出:1
29
30
31
提示:
32
33
3 <= nums.length <= 1000
34
1 <= nums[i] <= 109
35
题目保证 nums 删除一些元素后一定能得到山形数组。
Copied!

前置知识

  • 最长上升子序列

思路

看了下数据范围 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:
1
class Solution:
2
def minimumMountainRemovals(self, nums: List[int]) -> int:
3
n = len(nums)
4
ans = n
5
def LIS(A):
6
d = []
7
for a in A:
8
i = bisect.bisect_left(d, a)
9
if i < len(d):
10
d[i] = a
11
elif not d or d[-1] < a:
12
d.append(a)
13
return d.index(A[-1])
14
15
for i in range(1, n-1):
16
l, r = LIS(nums[:i+1]), LIS(nums[i:][::-1])
17
if not l or not r: continue
18
ans = min(ans, n - 1 - l - r)
19
return ans
Copied!
复杂度分析
令 N 为数组长度。
  • 时间复杂度:$O(N^2logN)$
  • 空间复杂度:$O(N)$
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 39K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。