问题描述
我们定义 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 <= 10001 <= nums[i] <= 109- 题目保证
nums 删除一些元素后一定能得到山形数组。
解题思路
分别记录从左到右和从右到左的的最长上升子序列即可。
\(\mathcal{O}(n^2)\) 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution:
def minimumMountainRemovals(self, nums: List[int]) -> int:
n = len(nums)
left, right = [1] * n, [1] * n
for i in range(1, n):
t = 0
for j in range(i):
if nums[i] > nums[j] and left[j] > t:
t = left[j]
left[i] = t + 1
for i in range(n - 2, -1, -1):
t = 0
for j in range(i + 1, n):
if nums[i] > nums[j] and right[j] > t:
t = right[j]
right[i] = t + 1
M = 0
for i in range(1, n - 1):
if left[i] >= 2 and right[i] >= 2:
M = max(M, left[i] + right[i] - 1)
return n - M
|
\(\mathcal{O}(n\log(n))\) 解法
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 | class Solution:
def minimumMountainRemovals(self, nums: List[int]) -> int:
def LIS(nums: List[int]) -> List[int]:
n = len(nums)
p = [1] * n
s = [nums[0]]
for i in range(1, n):
if nums[i] > s[-1]:
s.append(nums[i])
p[i] = len(s)
else:
L, R = 0, len(s)
while L < R:
M = (L + R) // 2
if nums[i] > s[M]:
L = M + 1
else:
R = M
s[L] = nums[i]
p[i] = L + 1
return p
left = LIS(nums)
right = LIS(nums[::-1])[::-1]
n = len(nums)
M = 0
for i in range(1, n - 1):
if left[i] >= 2 and right[i] >= 2:
M = max(M, left[i] + right[i] - 1)
return n - M
|