目标
给你一个数组 nums，你可以执行以下操作任意次数：
- 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
- 用它们的和替换这对元素。
返回将数组变为 非递减 所需的 最小操作次数 。
如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。
示例 1：
输入： nums = [5,2,3,1]
输出： 2
解释：
元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
元素对 (2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。示例 2：
输入： nums = [1,2,2]
输出： 0
解释：
数组 nums 已经是非递减的。说明：
- 1 <= nums.length <= 50
- -1000 <= nums[i] <= 1000
思路
有一个数组 nums，每一次操作可以将数组中和最小的相邻元素用它们的和替换掉，求使得数组非递减所需要的最少操作次数。
暴力解法是每次遍历找到和最小的数对 并替换，直到数组非递减。可以使用 next 数组模拟链表来删除元素。
代码
/**
* @date 2026-01-22 9:02
*/
public class MinimumPairRemoval3507 {
public int minimumPairRemoval_v1(int[] nums) {
int res = 0;
boolean decrease;
int n = nums.length;
int[] next = new int[n];
Arrays.setAll(next, i -> i + 1);
do {
decrease = false;
int index = 0, sum = Integer.MAX_VALUE;
for (int i = 0; next[i] < n; i = next[i]) {
if (nums[next[i]] < nums[i]) {
decrease = true;
}
int s = nums[i] + nums[next[i]];
if (s < sum) {
sum = s;
index = i;
}
}
if (decrease) {
nums[index] = sum;
next[index] = next[next[index]];
res++;
}
} while (decrease);
return res;
}
}
性能
