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-club.com.tw), 來自: 185.213.82.180 (臺灣) ※ 文章網址: https://ptt-club.com.tw/Marginalman/M.1730290860.A.2A2