leetcode
leetcode 1851 ~ 1900
从数组中移除最大值和最小值

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

难度:

标签:

题目描述

代码结果

运行时间: 63 ms, 内存: 26.8 MB


/*
 * 思路:
 * 1. 使用Java Stream API找到数组中的最小值和最大值的位置。
 * 2. 计算从数组前面移除最小值和最大值所需的删除次数。
 * 3. 计算从数组后面移除最小值和最大值所需的删除次数。
 * 4. 计算分别从前面移除一个值,从后面移除另一个值所需的删除次数。
 * 5. 返回上述三种情况中的最小值。
 */

import java.util.stream.IntStream;

public class Solution {
    public int minimumDeletions(int[] nums) {
        int n = nums.length;
        int minIndex = IntStream.range(0, n).reduce((i, j) -> nums[i] < nums[j] ? i : j).getAsInt();
        int maxIndex = IntStream.range(0, n).reduce((i, j) -> nums[i] > nums[j] ? i : j).getAsInt();

        int fromFront = Math.max(minIndex, maxIndex) + 1;
        int fromBack = Math.max(n - minIndex, n - maxIndex);
        int fromBothSides = Math.min(minIndex + 1 + n - maxIndex, maxIndex + 1 + n - minIndex);

        return Math.min(fromFront, Math.min(fromBack, fromBothSides));
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在找到最大值和最小值的索引后,需要检查并确保最小值索引l小于或等于最大值索引r?
这种检查是为了简化后续的删除操作计算。确保最小值索引 l 小于或等于最大值索引 r 可以避免在计算删除策略时处理索引重叠或颠倒的情况,从而使得计算更直观、逻辑更清晰。例如,如果我们需要从两端删除元素直到这两个值都被移除,确保 l ≤ r 可以帮助我们直接应用公式计算删除成本,而无需额外的条件判断。
🦆
在计算删除策略时,为什么考虑的是从前面删除到最大值索引、从后面删除到最小值索引以及先从前删除到最小值后从后删除到最大值这三种情况?是否存在其他可能的删除策略?
在考虑删除策略时,这三种方法基于最简单直接的路径来删除两个特定元素(最大值和最小值)。分别考虑从前端或后端开始删除是为了覆盖所有可能的最优解。同时,先删除一个端点的元素再删除另一个端点的元素可以确保在潜在的最小删除次数中选择。考虑其他策略如从中间某处开始切割然后再从两端删除,通常会导致不必要的额外操作,因此在实际应用中不是最优策略。
🦆
题解中提到的删除操作次数的计算方法中,(r + 1)、(n - l) 和 (l + 1 + n - r) 分别代表什么意义?它们是如何得出的?
(r + 1) 代表从数组开始到最大值索引的元素数量,即直接从前端删除到最大值包括最大值自身所需的操作次数。 (n - l) 表示从数组末端到最小值索引的元素数量,即直接从后端删除到最小值包括最小值自身所需的操作次数。 (l + 1 + n - r) 代表先从前端删除到最小值包括最小值自身,再从后端删除到最大值包括最大值自身所需的总操作次数。这些计算基于直接删除序列中连续的块以达到目标。
🦆
这种方法能否应对数组中有重复元素的情形?如果数组中元素不是互不相同的,该方法还适用吗?
此方法同样适用于数组中有重复元素的情况。函数 `index()` 返回的是第一个找到的指定值的索引,因此即便有重复的最大值或最小值,此方法依然能正确地返回第一次出现这些值的位置,并据此计算删除策略。然而,如果需要考虑所有的最大值和最小值,那么可能需要对方法进行扩展,以涵盖所有相关元素的索引,并重新考虑删除策略以确保最小删除次数。

相关问题