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

给你一个下标从 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 中的整数 互不相同

方法一：分类讨论

思路与算法

我们首先遍历数组，寻找到最大值与最小值对应的下标。为了方便起见，我们将两个下标中较小的记为 l，较大的记为 r。假设数组长度为 n，这两个下标将数组 nums 的其余部分分割成了三个互不相交的子数组（可能包含空数组），它们分别是 nums}[0..l-1], \textit{nums}[l+1..r-1], \textit{nums}[r+1..n-1] （其中 [a..b] 为闭区间）。

由于我们只能从数组首尾移除元素，因此移除最大值和最小值后的子数组一定为上述三块中某一块的子数组。因此如果想使得删除次数最小，那么移除完成后的子数组一定恰好为上述三个子数组之一，对应的删除次数即为数组长度 n 减去该子数组长度的差值。具体地：

• 移除完成后的子数组为 nums}[0..l-1]，此时删除次数为 n - l；

• 移除完成后的子数组为 nums}[l+1..r-1]，此时删除次数为 l + 1 + n - r；

• 移除完成后的子数组为 nums}[r+1..n-1]，此时删除次数为 r + 1。

而这三个差值的最小值即为最小的删除次数。我们返回该值作为答案。

代码

[sol1-C++]

class Solution {
public:
    int minimumDeletions(vector<int>& nums) {
        int n = nums.size();
        int minidx = min_element(nums.begin(), nums.end()) - nums.begin();
        int maxidx = max_element(nums.begin(), nums.end()) - nums.begin();
        int l = min(minidx, maxidx);   // 最值下标中的较小值
        int r = max(minidx, maxidx);   // 最值下标中的较大值
        return min({r + 1, n - l, l + 1 + n - r});   // 计算三种情况下删除次数的最小值
    }
};

[sol1-Python3]

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        minidx = nums.index(min(nums))
        maxidx = nums.index(max(nums))
        l = min(minidx, maxidx)   # 最值下标中的较小值
        r = max(minidx, maxidx)   # 最值下标中的较大值
        n = len(nums)
        return min(r + 1, n - l, l + 1 + n - r)   # 计算三种情况下删除次数的最小值

复杂度分析

• 时间复杂度：O(n)，其中 n 为 nums 的长度。即为计算最小删除次数的时间复杂度。

• 空间复杂度：O(1)。