A7010. 得到山形数组的最少删除次数
编程题
普及/提高-
知识点
题目描述
我们定义数组 $a$ 是 **山形数组** 当且仅当它满足以下条件：
1. 数组长度 $n \ge 3$。
2. 存在某个下标 $i$（$0 < i < n - 1$），使得：
$$a_0 < a_1 < \dots < a_{i - 1} < a_i$$
$$a_i > a_{i + 1} > \dots > a_{n - 1}$$
换句话说，山形数组的元素先严格递增，达到一个峰值后，再严格递减。
现在给你一个整数数组 $a$，请你返回将 $a$ 变成 **山形数组** 所需的 **最少** 删除次数。
题目保证 $a$ 在删除一些元素后，一定能得到一个山形数组。
1. 数组长度 $n \ge 3$。
2. 存在某个下标 $i$（$0 < i < n - 1$），使得：
$$a_0 < a_1 < \dots < a_{i - 1} < a_i$$
$$a_i > a_{i + 1} > \dots > a_{n - 1}$$
换句话说，山形数组的元素先严格递增，达到一个峰值后，再严格递减。
现在给你一个整数数组 $a$，请你返回将 $a$ 变成 **山形数组** 所需的 **最少** 删除次数。
题目保证 $a$ 在删除一些元素后，一定能得到一个山形数组。
输入格式
第一行包含一个整数 $n$，表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组的元素。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组的元素。
输出格式
输出一个整数，表示最少删除次数。
输入输出样例
输入 #1
3 1 3 1
输出 #1
0
输入 #2
8 2 1 1 5 6 2 3 1
输出 #2
3
说明/提示
**【样例解释 1】**
数组
**【样例解释 2】**
一种可行的方法是将下标为 0，1 和 5 的元素删除，剩余元素为
删除的元素为
**【数据范围】**
对于 $100\%$ 的数据，满足：
- $3 \le n \le 1000$
- $1 \le a_i \le 10^9$
- 题目保证输入数据中一定存在合法的山形子序列。
数组
[1, 3, 1] 本身就是山形数组，所以不需要删除任何元素。**【样例解释 2】**
一种可行的方法是将下标为 0，1 和 5 的元素删除，剩余元素为
[1, 5, 6, 3, 1]，这是一个山形数组。删除的元素为
2, 1, 2。**【数据范围】**
对于 $100\%$ 的数据，满足：
- $3 \le n \le 1000$
- $1 \le a_i \le 10^9$
- 题目保证输入数据中一定存在合法的山形子序列。