从数组中移除最大值和最小值

标签: 贪心 数组

难度: Medium

给你一个下标从 0 开始的数组 nums ，数组由若干 互不相同 的整数组成。

nums 中有一个值最小的元素和一个值最大的元素。分别称为 最小值 和 最大值 。你的目标是从数组中移除这两个元素。

一次 删除 操作定义为从数组的 前面 移除一个元素或从数组的 后面 移除一个元素。

返回将数组中最小值和最大值 都 移除需要的最小删除次数。

示例 1：

输入：nums = [2,10,7,5,4,1,8,6]
输出：5
解释：
数组中的最小元素是 nums[5] ，值为 1 。
数组中的最大元素是 nums[1] ，值为 10 。
将最大值和最小值都移除需要从数组前面移除 2 个元素，从数组后面移除 3 个元素。
结果是 2 + 3 = 5 ，这是所有可能情况中的最小删除次数。

示例 2：

输入：nums = [0,-4,19,1,8,-2,-3,5]
输出：3
解释：
数组中的最小元素是 nums[1] ，值为 -4 。
数组中的最大元素是 nums[2] ，值为 19 。
将最大值和最小值都移除需要从数组前面移除 3 个元素。
结果是 3 ，这是所有可能情况中的最小删除次数。

示例 3：

输入：nums = [101]
输出：1
解释：
数组中只有这一个元素，那么它既是数组中的最小值又是数组中的最大值。
移除它只需要 1 次删除操作。

提示：

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105
  • nums 中的整数 互不相同

Submission

运行时间: 63 ms

内存: 26.8 MB

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        n = len(nums)
        # if n==1:return 1
        r = nums.index(max(nums))
        l = nums.index(min(nums))
        if l>r:l,r=r,l
        return min((r + 1), (n - l), (l + 1 + n - r))

Explain

此题解首先通过查找数组中的最大值和最小值的索引（r和l）。如果最小值索引大于最大值索引，就交换这两者，以确保l（最小值索引）小于或等于r（最大值索引）。然后计算移除这两个值的最小操作次数，有三种可能的策略：1) 从数组前面直接删除到最大值（r+1）；2) 从数组后面直接删除到最小值（n-l，其中n是数组长度）；3) 从前面删除到最小值后从后面删除到最大值（(l+1) + (n-r)）。取这三种策略的最小值即为结果。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        n = len(nums)  # 获取数组长度
        r = nums.index(max(nums))  # 找到最大值的索引
        l = nums.index(min(nums))  # 找到最小值的索引
        if l > r: l, r = r, l  # 确保l为最小索引，r为最大索引
        return min((r + 1), (n - l), (l + 1 + n - r))  # 返回三种删除策略的最小值

Explore

这种检查是为了简化后续的删除操作计算。确保最小值索引 l 小于或等于最大值索引 r 可以避免在计算删除策略时处理索引重叠或颠倒的情况，从而使得计算更直观、逻辑更清晰。例如，如果我们需要从两端删除元素直到这两个值都被移除，确保 l ≤ r 可以帮助我们直接应用公式计算删除成本，而无需额外的条件判断。

在考虑删除策略时，这三种方法基于最简单直接的路径来删除两个特定元素（最大值和最小值）。分别考虑从前端或后端开始删除是为了覆盖所有可能的最优解。同时，先删除一个端点的元素再删除另一个端点的元素可以确保在潜在的最小删除次数中选择。考虑其他策略如从中间某处开始切割然后再从两端删除，通常会导致不必要的额外操作，因此在实际应用中不是最优策略。

(r + 1) 代表从数组开始到最大值索引的元素数量，即直接从前端删除到最大值包括最大值自身所需的操作次数。 (n - l) 表示从数组末端到最小值索引的元素数量，即直接从后端删除到最小值包括最小值自身所需的操作次数。 (l + 1 + n - r) 代表先从前端删除到最小值包括最小值自身，再从后端删除到最大值包括最大值自身所需的总操作次数。这些计算基于直接删除序列中连续的块以达到目标。

此方法同样适用于数组中有重复元素的情况。函数 `index()` 返回的是第一个找到的指定值的索引，因此即便有重复的最大值或最小值，此方法依然能正确地返回第一次出现这些值的位置，并据此计算删除策略。然而，如果需要考虑所有的最大值和最小值，那么可能需要对方法进行扩展，以涵盖所有相关元素的索引，并重新考虑删除策略以确保最小删除次数。