Medium

题目描述

给你一个正整数数组 nums。

对于正整数 k，定义 nonPositive(nums, k) 为使数组 nums 中每个元素都变为非正数所需的最少操作次数。在一次操作中，你可以选择一个下标 i 并将 nums[i] 减少 k。

返回一个整数，表示使得 nonPositive(nums, k) <= k² 的最小 k 值。

示例 1：

输入：nums = [3,7,5]
输出：3
解释：
当 k = 3 时，nonPositive(nums, k) = 6 <= k²。
- 将 nums[0] = 3 减少 1 次。nums[0] 变为 3 - 3 = 0。
- 将 nums[1] = 7 减少 3 次。nums[1] 变为 7 - 3 - 3 - 3 = -2。
- 将 nums[2] = 5 减少 2 次。nums[2] 变为 5 - 3 - 3 = -1。

示例 2：

输入：nums = [1]
输出：1
解释：
当 k = 1 时，nonPositive(nums, k) = 1 <= k²。
- 将 nums[0] = 1 减少 1 次。nums[0] 变为 1 - 1 = 0。

约束：

  • 1 <= nums.length <= 10⁵
  • 1 <= nums[i] <= 10⁵

解题思路

这道题的核心在于找到满足条件的最小 k 值。我们需要理解两个关键概念：

  1. 操作次数计算：对于给定的 k，要使 nums[i] 变为非正数，需要的操作次数是 ⌈nums[i] / k⌉（向上取整）
  2. 二分查找优化：由于 k 值具有单调性（k 越大，总操作次数越小），我们可以使用二分查找

解题思路：

  • 使用二分查找在 [1, max(nums)] 范围内寻找最小的 k
  • 对于每个候选 k，计算 nonPositive(nums, k)，即所有元素需要的操作次数之和
  • 检查是否满足 nonPositive(nums, k) ≤ k²
  • 如果满足条件，尝试更小的 k；否则增大 k

时间复杂度优化：

  • 二分查找的范围是 [1, max(nums)]，最多需要 log(max(nums)) 次迭代
  • 每次检查需要遍历数组计算总操作次数，时间复杂度 O(n)
  • 总体时间复杂度：O(n × log(max(nums)))

这种方法比暴力枚举所有可能的 k 值要高效得多。

代码实现

class Solution {
public:
    int minimumK(vector<int>& nums) {
        int left = 1, right = *max_element(nums.begin(), nums.end());
        int result = right;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long long operations = 0;
            
            for (int num : nums) {
                operations += (num + mid - 1) / mid;  // 向上取整
            }
            
            if (operations <= (long long)mid * mid) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def minimumK(self, nums: List[int]) -> int:
        left, right = 1, max(nums)
        result = right
        
        while left <= right:
            mid = (left + right) // 2
            operations = 0
            
            for num in nums:
                operations += (num + mid - 1) // mid  # 向上取整
            
            if operations <= mid * mid:
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return result

public class Solution {
    public int MinimumK(int[] nums) {
        int left = 1, right = nums.Max();
        int result = right;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long operations = 0;
            
            foreach (int num in nums) {
                operations += (num + mid - 1) / mid;  // 向上取整
            }
            
            if (operations <= (long)mid * mid) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
}

var minimumK = function(nums) {
    let left = 1, right = Math.max(...nums);
    let result = right;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let operations = 0;
        
        for (let num of nums) {
            operations += Math.ceil(num / mid);
        }
        
        if (operations <= mid * mid) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × log(max(nums)))
空间复杂度O(1)

其中 n 是数组长度，max(nums) 是数组中的最大值。二分查找需要 log(max(nums)) 次迭代，每次需要 O(n) 时间计算操作次数。