作者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/m.aspx?n=bbs/Marginalman/M.1730290860.A.2A2.html