5940. 从数组中移除最大值和最小值
程序员文章站
2023-12-26 16:24:10
...
给你一个下标从 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、中右两边都取
code:
class Solution {
public int minimumDeletions(int[] nums) {
int minResult = Integer.MAX_VALUE;
int min = Integer.MAX_VALUE;
int minIndex = 0;
int max = Integer.MIN_VALUE;
int maxIndex = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
maxIndex = i;
}
if (nums[i] < min) {
min = nums[i];
minIndex = i;
}
}
if (maxIndex < minIndex) {
int tmp = maxIndex;
maxIndex = minIndex;
minIndex = tmp;
}
int start = 0;
int end = nums.length - 1;
int result1 = (minIndex - start + 1) + (end - maxIndex + 1);
minResult = Math.min(result1, minResult);
int result2 = maxIndex + 1;
minResult = Math.min(result2, minResult);
int result3 = end - minIndex + 1;
minResult = Math.min(result3, minResult);
return minResult;
}
}