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

链接

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 <= 10e5
• -10e5 <= nums[i] <= 10e5
• nums 中的整数 互不相同

思路

1. 遍历数组，找出最大值下标和最小值下标。

2. 判断两个下标前后顺序，让min_index在前，max_index在后。

3. 结果为三种情况的最小值：

• 1）全部从左边删除，也就是删掉所有max_index前（包括max_index）的元素。
• 2)  全部从右边删除，也就是删掉所有min_index后（包括min_index）的元素。
• 3) min_index从左边删，max_index从右边删。

C++ Code

class Solution {
public:
    int minimumDeletions(vector<int>& nums) {
        //寻找最大和最小的下标
        int max=-10e6,max_index=0;
        int min=10e6,min_index=0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]>max) {max=nums[i]; max_index=i;}
            if(nums[i]<min) {min=nums[i]; min_index=i;} 
        }
        if(max_index<min_index) 
        {
            swap(max_index,min_index);
        }
        int a=max_index+1; //从前面删除
        int b=nums.size()-min_index; //从后面删除
        int c=min_index+1+nums.size()-max_index; //从两边删除
        if(a<=b) return a<=c?a:c;
        else return b<=c?b:c;
    }
};