题目描述：
我们定义 arr 是 山形数组 当且仅当它满足：
给你整数数组 nums ，请你返回将 nums 变成 山形状数组 的 最少 删除次数。
数据范围：
$3\le nums.len \le 1000, 1\le nums[i] \le 10^9$
题解：
可以发现是一个单调上升子序列问题，而且是严格上升。只需要找一下以每个位置结尾的单调上升子序列的长度即可。
刚好可以左边一遍，右边一遍。
可以选择使用二分的做法， $dp[len]$ 表示长度为 $len$ 的子序列末尾最小数字，然后对于 $nums[i]$ 如果可以直接接在 $dp[len]$ 末尾，那么就 dp[++len] = nums[i]。不能接的话说明 $nums[i] < dp[len]$ ，可以从前面找出来末尾字符比 $nums[i]$ 大的，使用 $lower\_bound(dp + 1, dp + 1 + len + 1, nums[i])$ 找到下标 $index$ ，然后修改长度为 $index$ 的末尾数字为 $nums[i]$ 。
最后需要注意的是，最后的数组的长度要大于等于 $3$ ，而且需要满足，山峰不在左右端点处，因此需要判断 $left[i] > 1$ ， $right[i] > 1$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minimumMountainRemovals(vector<int> &nums)
{
int n = nums.size();
vector<int> left(n), right(n);
vector<int> a(n);
a[0] = nums[0];
int len = 1;
left[0] = len;
for (int i = 1; i < n; ++i)
{
if (nums[i] > a[len - 1])
a[len++] = nums[i];
else
{
int index = lower_bound(a.begin(), a.begin() + len, nums[i]) - a.begin();
a[index] = nums[i];
}
left[i] = len;
}
len = 1;
right[n - 1] = len;
a[0] = nums[n - 1];
for (int i = n - 2; i >= 0; --i)
{
if (nums[i] > a[len - 1])
a[len++] = nums[i];
else
{
int index = lower_bound(a.begin(), a.begin() + len, nums[i]) - a.begin();
a[index] = nums[i];
}
right[i] = len;
}
int ans = n;
for (int i = 1; i < n - 1; ++i)
{
if (left[i] > 1 && right[i] > 1)
{
ans = min(ans, n - left[i] - right[i] + 1);
}
}
return ans;
}
};
|