从数组中移除最大值和最小值
难度:
标签:
题目描述
代码结果
运行时间: 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?
▷🦆
在计算删除策略时,为什么考虑的是从前面删除到最大值索引、从后面删除到最小值索引以及先从前删除到最小值后从后删除到最大值这三种情况?是否存在其他可能的删除策略?
▷🦆
题解中提到的删除操作次数的计算方法中,(r + 1)、(n - l) 和 (l + 1 + n - r) 分别代表什么意义?它们是如何得出的?
▷🦆
这种方法能否应对数组中有重复元素的情形?如果数组中元素不是互不相同的,该方法还适用吗?
▷