Easy

题目描述

给定一个数组 nums，你可以执行以下操作任意次数：

  • 选择 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

提示：

  • 模拟操作过程

解题思路

这道题要求我们通过合并相邻元素使数组变为非递减序列，每次选择和最小的相邻对进行合并。

解题思路：

  1. 模拟过程：按照题目要求，重复执行以下步骤直到数组变为非递减：

    • 检查数组是否已经非递减，如果是则结束
    • 找到所有相邻对的和，选择最小的那个（如果有多个最小值选最左边的）
    • 将选中的相邻对替换为它们的和
    • 操作计数器加1

  2. 实现细节：

    • 用一个函数检查数组是否非递减
    • 遍历数组找到最小和的相邻对的位置
    • 删除两个元素并插入它们的和
    • 重复直到数组有序

  3. 时间复杂度：由于数组长度最多50，每次操作会减少一个元素，最多需要49次操作。每次操作需要O(n)时间找到最小和并更新数组，总体复杂度是可接受的。

这个解法直接模拟题目描述的过程，逻辑清晰且易于理解。

代码实现

class Solution {
public:
    int minimumPairRemoval(vector<int>& nums) {
        int operations = 0;
        
        while (!isNonDecreasing(nums)) {
            int minSum = INT_MAX;
            int minIndex = -1;
            
            // 找到最小和的相邻对
            for (int i = 0; i < nums.size() - 1; i++) {
                int sum = nums[i] + nums[i + 1];
                if (sum < minSum) {
                    minSum = sum;
                    minIndex = i;
                }
            }
            
            // 合并相邻对
            nums[minIndex] = minSum;
            nums.erase(nums.begin() + minIndex + 1);
            operations++;
        }
        
        return operations;
    }
    
private:
    bool isNonDecreasing(const vector<int>& nums) {
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                return false;
            }
        }
        return true;
    }
};

class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        operations = 0
        
        while not self.is_non_decreasing(nums):
            min_sum = float('inf')
            min_index = -1
            
            # 找到最小和的相邻对
            for i in range(len(nums) - 1):
                current_sum = nums[i] + nums[i + 1]
                if current_sum < min_sum:
                    min_sum = current_sum
                    min_index = i
            
            # 合并相邻对
            nums[min_index] = min_sum
            nums.pop(min_index + 1)
            operations += 1
        
        return operations
    
    def is_non_decreasing(self, nums):
        for i in range(1, len(nums)):
            if nums[i] < nums[i - 1]:
                return False
        return True

public class Solution {
    public int MinimumPairRemoval(int[] nums) {
        var numsList = new List<int>(nums);
        int operations = 0;
        
        while (!IsNonDecreasing(numsList)) {
            int minSum = int.MaxValue;
            int minIndex = -1;
            
            // 找到最小和的相邻对
            for (int i = 0; i < numsList.Count - 1; i++) {
                int sum = numsList[i] + numsList[i + 1];
                if (sum < minSum) {
                    minSum = sum;
                    minIndex = i;
                }
            }
            
            // 合并相邻对
            numsList[minIndex] = minSum;
            numsList.RemoveAt(minIndex + 1);
            operations++;
        }
        
        return operations;
    }
    
    private bool IsNonDecreasing(List<int> nums) {
        for (int i = 1; i < nums.Count; i++) {
            if (nums[i] < nums[i - 1]) {
                return false;
            }
        }
        return true;
    }
}

var minimumPairRemoval = function(nums) {
    let operations = 0;
    
    while (!isNonDecreasing(nums)) {
        let minSum = Infinity;
        let minIndex = -1;
        
        // 找到最小和的相邻对
        for (let i = 0; i < nums.length - 1; i++) {
            let sum = nums[i] + nums[i + 1];
            if (sum < minSum) {
                minSum = sum;
                minIndex = i;
            }
        }
        
        // 合并相邻对
        nums[minIndex] = minSum;
        nums.splice(minIndex + 1, 1);
        operations++;
    }
    
    return operations;
    
    function isNonDecreasing(arr) {
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                return false;
            }
        }
        return true;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n³) - 最多需要 n-1 次操作，每次操作需要 O(n) 时间找最小和，O(n) 时间检查是否有序
空间复杂度O(1) - 只使用常数额外空间（不考虑输入数组的修改）