# 1671. 得到山形数组的最少删除次数
### 题目地址（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 = [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`。直接莽过没问题。
这道题需要你有最长上升子序列的知识。如果你还不清楚，建议看下我之前写的文章 [穿上衣服我就不认识你了？来聊聊最长上升子序列](https://lucifer.ren/blog/2020/06/20/LIS/)
有了这样的一个知识前提，我们可以枚举所有的山顶。那么
* 左侧需要删除的个数其实就是 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:
```py
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)$
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 39K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1671.minimum-number-of-removals-to-make-mountain-array.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.