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

解题思路

这道题的核心思路是贪心策略。由于只能从数组的前面或后面删除元素，我们需要考虑三种删除策略：

策略分析：

  1. 从前面删除两个元素：删除次数为 max(minIndex, maxIndex) + 1
  2. 从后面删除两个元素：删除次数为 n - min(minIndex, maxIndex)
  3. 一前一后删除：删除次数为 (minIndex + 1) + (n - maxIndex) 或 (maxIndex + 1) + (n - minIndex)

算法步骤：

  1. 首先遍历数组，找到最小值和最大值的索引位置
  2. 计算三种策略的删除次数：
    • 全部从前面删除：需要删除到较远的那个元素位置
    • 全部从后面删除：需要删除到较近的那个元素位置
    • 分别从前后删除：最小值从一端删除，最大值从另一端删除
  3. 返回三种策略中的最小值

这种贪心策略能保证找到全局最优解，因为我们穷举了所有可能的删除方案。时间复杂度为O(n)，空间复杂度为O(1)。

代码实现

class Solution {
public:
    int minimumDeletions(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 1;
        
        int minIndex = 0, maxIndex = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[minIndex]) minIndex = i;
            if (nums[i] > nums[maxIndex]) maxIndex = i;
        }
        
        // 策略1：从前面删除两个元素
        int fromFront = max(minIndex, maxIndex) + 1;
        
        // 策略2：从后面删除两个元素  
        int fromBack = n - min(minIndex, maxIndex);
        
        // 策略3：一前一后删除
        int frontAndBack = (minIndex + 1) + (n - maxIndex);
        int backAndFront = (maxIndex + 1) + (n - minIndex);
        
        return min({fromFront, fromBack, frontAndBack, backAndFront});
    }
};

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 1
        
        min_index = nums.index(min(nums))
        max_index = nums.index(max(nums))
        
        # 策略1：从前面删除两个元素
        from_front = max(min_index, max_index) + 1
        
        # 策略2：从后面删除两个元素
        from_back = n - min(min_index, max_index)
        
        # 策略3：一前一后删除
        front_and_back = (min_index + 1) + (n - max_index)
        back_and_front = (max_index + 1) + (n - min_index)
        
        return min(from_front, from_back, front_and_back, back_and_front)

public class Solution {
    public int MinimumDeletions(int[] nums) {
        int n = nums.Length;
        if (n == 1) return 1;
        
        int minIndex = 0, maxIndex = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[minIndex]) minIndex = i;
            if (nums[i] > nums[maxIndex]) maxIndex = i;
        }
        
        // 策略1：从前面删除两个元素
        int fromFront = Math.Max(minIndex, maxIndex) + 1;
        
        // 策略2：从后面删除两个元素
        int fromBack = n - Math.Min(minIndex, maxIndex);
        
        // 策略3：一前一后删除
        int frontAndBack = (minIndex + 1) + (n - maxIndex);
        int backAndFront = (maxIndex + 1) + (n - minIndex);
        
        return Math.Min(Math.Min(fromFront, fromBack), Math.Min(frontAndBack, backAndFront));
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDeletions = function(nums) {
    if (nums.length === 1) return 1;
    
    let minIdx = 0, maxIdx = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] < nums[minIdx]) minIdx = i;
        if (nums[i] > nums[maxIdx]) maxIdx = i;
    }
    
    const n = nums.length;
    const fromLeft = Math.max(minIdx + 1, maxIdx + 1);
    const fromRight = Math.max(n - minIdx, n - maxIdx);
    const mixed = Math.min(minIdx + 1, maxIdx + 1) + Math.min(n - minIdx, n - maxIdx);
    
    return Math.min(fromLeft, fromRight, mixed);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次找到最小值和最大值的索引
空间复杂度O(1)只使用了常数级别的额外空间存储索引和计算结果

相关题目