力扣2025周赛题题解
2025-04
第 444 场周赛
Q1. 移除最小数对使数组有序 I（20250406）
给你一个数组
nums，你可以执行以下操作任意次数：
- 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
- 用它们的和替换这对元素。
返回将数组变为 非递减 所需的 最小操作次数 。
如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。
面临的问题：
如何将计算出来的值在赋值到原数组上，比如nums=[5,2,3,1]，如何将3+1=4的值放入数组？
- 通过使用List的api， remove(lit, index)来实现
如何找到最小的靠左的数对？比如nums=[5,2,3,1]，如何确定3+1是最小的？
- 每次循环，将最小的数对记录下来。
Java
class Solution {
public int minimumPairRemoval(int[] nums) {
List<Integer> newnums = new ArrayList<>();
for (int x : nums) {
newnums.add(x);
}
int ans = 0;
// 循环判断
while (!hasSort(newnums)) {
int index = ansIdx(newnums);
int sum = newnums.get(index) + newnums.get(index + 1);
newnums.remove(index + 1);
newnums.set(index, sum);
ans++;
}
return ans;
}
// 判断数组是否有序
boolean hasSort(List<Integer> nums) {
if (nums.size() == 1) {
return true;
}
for (int i = 0; i < nums.size() - 1; i++) {
if (nums.get(i) > nums.get(i + 1)) {
return false;
}
}
return true;
}
// 返回最小数对的下标
int ansIdx(List<Integer> nums) {
int minvalue = nums.get(0) + nums.get(1);
int minindex = 0;
for (int i = 1; i < nums.size() - 1; i++) {
int tmp = nums.get(i) + nums.get(i + 1);
if (tmp < minvalue) {
minvalue = tmp;
minindex = i;
}
}
return minindex;
}
}