Leetcode 1671. Minimum Number of Removals to Make Mountain Array

迷南。 2022-09-09 00:13 250阅读 0赞

文章作者:Tyan
博客:noahsnail.com | CSDN | 简书

1. Description

Minimum Number of Removals to Make Mountain Array

2. Solution

**解析:**Version 1,分别以数组中的元素作为中心点,在左右两侧分别求最长递增子序列,根据左右两侧的最长递增子序列的长度求出山脉的长度,则要删除的元素个数为数组长度减去最长的山脉长度,速度太慢。Version 2在Version 1的基础上进行了优化,分别求出数组正序和逆序各个位置的最长递增子序列,然后跟Version 1类似,累加左右对应位置的最长递增子序列的长度,即为山脉的长度,则要删除的元素个数为数组长度减去最长的山脉长度,速度明显有了大幅提升。

  • Version 1

    class Solution:

    1. def minimumMountainRemovals(self, nums: List[int]) -> int:
    2. n = len(nums)
    3. maximum = 0
    4. for index in range(1, n - 1):
    5. left = [nums[index]]
    6. for i in range(index - 1, -1, -1):
    7. if nums[i] >= nums[index] or nums[i] == left[0]:
    8. continue
    9. elif nums[i] < left[0]:
    10. bisect.insort(left, nums[i])
    11. else:
    12. pos = bisect.bisect(left, nums[i])
    13. left[pos-1] = nums[i]
    14. if len(left) < 2:
    15. continue
    16. right = [nums[index]]
    17. for i in range(index+1, n):
    18. if nums[i] >= nums[index] or nums[i] == right[0]:
    19. continue
    20. if nums[i] < right[0]:
    21. bisect.insort(right, nums[i])
    22. else:
    23. pos = bisect.bisect(right, nums[i])
    24. right[pos-1] = nums[i]
    25. if len(right) > 1:
    26. maximum = max(maximum, len(left) + len(right) - 1)
    27. return n - maximum
  • Version 2

    class Solution:

    1. def minimumMountainRemovals(self, nums: List[int]) -> int:
    2. n = len(nums)
    3. maximum = 0
    4. left = self.LIS(nums)
    5. right = self.LIS(nums[::-1])
    6. for i in range(n):
    7. if left[i] > 1 and right[n-i-1] > 1:
    8. maximum = max(maximum, left[i] + right[n-i-1] - 1)
    9. return n - maximum
  1. def LIS(self, nums):
  2. n = len(nums)
  3. dp = [1] * n
  4. arr = [nums[0]]
  5. for i in range(1, n):
  6. if nums[i] > arr[-1]:
  7. arr.append(nums[i])
  8. else:
  9. pos = bisect.bisect_left(arr, nums[i])
  10. arr[pos] = nums[i]
  11. dp[i] = len(arr)
  12. return dp

Reference

  1. https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/

发表评论

表情:
评论列表 (有 0 条评论,250人围观)

还没有评论,来说两句吧...

相关阅读