2091.从数组中移除最大值和最小值：三种可能取最小

【LetMeFly】2091.从数组中移除最大值和最小值：三种可能取最小

力扣题目链接：https://leetcode.cn/problems/removing-minimum-and-maximum-from-array/

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

解题方法：一次遍历

一次遍历即可得到最大元素和最小元素的位置。最优的删除两下标的方式有三种：

1. 从左往右删完两个下标
2. 从右往左删完两个下标
3. 从两边开始分别删掉两个下标

以上。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-08-30 09:44:30
 */
class Solution {
public:
    int minimumDeletions(vector<int>& nums) {
        int m = nums[0], M = m;
        int im = 0, iM = 0;
        int n = nums.size();
        for (int i = 1; i < n; i++) {
            if (nums[i] < m) {
                m = nums[i];
                im = i;
            }
            if (nums[i] > M) {
                M = nums[i];
                iM = i;
            }
        }

        if (im > iM) {
            swap(im, iM);
        }
        return min(im + 1 + n - iM, min(iM + 1, n - im));
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源