We define arr to be a mountain array if and only if it satisfies:
arr.length >= 3
There is a subscript i (starting from 0) that satisfies 0 < i < arrlength - 1 and:
arr[0] arr[i] >arr[i + 1] >arr[arr.length - 1]
Given an array of integers nums, please return the minimum number of times to delete nums into a mountain-shaped array.
Example 1: Input: nums = [1,3,1].
Output: 0 Explanation: The array itself is a mountain array, so we don't need to remove any elements.
Example 2: Input: nums = [2,1,1,5,6,2,3,1].
Output: 3 Explanation: One way is to remove the elements with the subscripts 0,1 and 5, and the remaining elements are [1,5,6,3,1], which is the mountain array.
Example 3: Input: nums = [4,3,2,1,1,2,3,1].
Output: 4 hints:
Input: nums = [1,2,3,4,4,3,2,1].
Output: 1 Hint:
3 <= nums.length <= 1000
1 <= nums[i] <= 109
The problem guarantees that nums will get the mountain array after removing some elements.
The longest ascending subseries looks at the data range3 <= nums.length <= 1000。It's no problem to be reckless.
This question requires you to have knowledge of the longest ascending subsequence.
With such an intellectual premise, we can enumerate all the mountaintops. So.
The number of items that need to be deleted on the left side is actually l - lis left, where l is the length of the left side and lis left is the length of the longest ascending subsequence on the left. The number of items that need to be deleted on the right side is actually r - lds right, where r is the length of the right side and lds right is the length of the longest descending subsequence on the right. In order to unify the logic intoLongest ascending subsequence length, we can flip r over once.
The time complexity of enumerating the summit is $o(n)$ and the regular LIS complexity is $o(n2)$.
Cheat sheet based on time complexity:
The time complexity cheat sheet can be found in my brushing plugin. The brushing plug-in can be obtained in my *** force deduction plus plus" reply plugin.The data range for this question is < = 1000. Therefore $n 3$ cannot be passed. However, we can use greedy lis, which has a time complexity of $n 2logn$, which is barely passable. Regarding the greedy solution lis, it is also mentioned in the above article.
* Support: python3
python3 code:
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] so that n is the length of the array.
Time complexity: $o(n 2logn)$Space complexity: $o(n)$