作者dont (dont)
看板Marginalman
标题Re: [闲聊] 每日leetcode
时间Wed Oct 30 20:20:58 2024
1671. Minimum Number of Removals to Make Mountain Array
## 思路
左右各做一次LIS, 并记录在idx时的LIS长度
Mountain array的长度会是 LIS长度 + LDS长度 - 1
e.g. 12321
LIS=123 len=3
LDS=321 len=3
计算最少删去个数时要跳过LIS/LDS长度1的case
## Code
```python
class Solution:
def minimumMountainRemovals(self, nums: List[int]) -> int:
n = len(nums)
def binary_search(arr, num):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] >= num:
right = mid
else:
left = mid + 1
return left
lis = []
lis_len = [1] * n
for i in range(n):
j = binary_search(lis, nums[i])
if j == len(lis):
lis.append(nums[i])
else:
lis[j] = nums[i]
lis_len[i] = len(lis)
lds = []
lds_len = [1] * n
for i in range(n-1, -1, -1):
j = binary_search(lds, nums[i])
if j == len(lds):
lds.append(nums[i])
else:
lds[j] = nums[i]
lds_len[i] = len(lds)
res = n
for v1, v2 in zip(lis_len, lds_len):
if v1 > 1 and v2 > 1:
res = min(res, n - v1 - v2 + 1)
return res
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 185.213.82.180 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Marginalman/M.1730290860.A.2A2.html