日期: 2026年1月22日

目标

给你一个数组 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;
    }

}

性能