Medium

题目描述

给定一个整数 mountainHeight，表示山峰的高度。

还给定一个整数数组 workerTimes，表示工人的工作时间（以秒为单位）。

工人们同时工作来降低山峰的高度。对于工人 i：

  • 要将山峰的高度降低 x，需要 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x 秒。例如：
    • 要将山峰的高度降低 1，需要 workerTimes[i] 秒。
    • 要将山峰的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，以此类推。

返回一个整数，表示工人们使山峰高度变为 0 所需的最小秒数。

示例 1：

输入：mountainHeight = 4, workerTimes = [2,1,1]
输出：3
解释：
山峰高度可以降低到 0 的一种方式是：
- 工人 0 降低高度 1，耗时 workerTimes[0] = 2 秒。
- 工人 1 降低高度 2，耗时 workerTimes[1] + workerTimes[1] * 2 = 3 秒。
- 工人 2 降低高度 1，耗时 workerTimes[2] = 1 秒。
由于他们同时工作，所需的最小时间是 max(2, 3, 1) = 3 秒。

示例 2：

输入：mountainHeight = 10, workerTimes = [3,2,2,4]
输出：12

示例 3：

输入：mountainHeight = 5, workerTimes = [1]
输出：15

约束条件：

  • 1 <= mountainHeight <= 10^5
  • 1 <= workerTimes.length <= 10^4
  • 1 <= workerTimes[i] <= 10^6

解题思路

这道题的核心思路是使用二分搜索 + 贪心算法来求解最小时间。

解题思路：

  1. 关键观察：工人 i 降低高度 x 所需的时间为 workerTimes[i] * (1 + 2 + ... + x) = workerTimes[i] * x * (x + 1) / 2。这是一个关于 x 的二次函数。

  2. 二分搜索：我们可以二分搜索答案的时间 t。对于每个时间 t，检查是否能在时间 t 内将山峰高度降为 0。

  3. 检查函数：给定时间 t，对每个工人 i，我们需要找到在时间 t 内该工人能降低的最大高度。这需要求解不等式：workerTimes[i] * x * (x + 1) / 2 ≤ t，解得 x 的最大整数值。

  4. 贪心策略：每个工人都尽可能多地降低高度，然后检查总的降低高度是否不小于 mountainHeight。

  5. 优化技巧：

    • 使用数学公式求解二次不等式，避免线性搜索
    • 二分搜索的上界可以设为单个工人完成所有工作所需的时间

时间复杂度分析：

  • 二分搜索：O(log(上界))
  • 每次检查：O(n)，其中 n 是工人数量
  • 总体：O(n * log(上界))

代码实现

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        long long left = 1;
        long long right = 1LL * mountainHeight * (mountainHeight + 1) / 2 * (*min_element(workerTimes.begin(), workerTimes.end()));
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (canFinish(mid, mountainHeight, workerTimes)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
private:
    bool canFinish(long long time, int mountainHeight, vector<int>& workerTimes) {
        long long totalReduction = 0;
        for (int workerTime : workerTimes) {
            long long maxHeight = getMaxHeight(time, workerTime);
            totalReduction += maxHeight;
            if (totalReduction >= mountainHeight) {
                return true;
            }
        }
        return totalReduction >= mountainHeight;
    }
    
    long long getMaxHeight(long long time, int workerTime) {
        // Solve: workerTime * x * (x + 1) / 2 <= time
        // x^2 + x <= 2 * time / workerTime
        long long limit = 2 * time / workerTime;
        long long x = (long long)sqrt(limit);
        
        // Check x and x+1 to find the exact answer
        while (x * (x + 1) <= limit) x++;
        while (x * (x + 1) > limit) x--;
        
        return x;
    }
};

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        def can_finish(time):
            total_reduction = 0
            for worker_time in workerTimes:
                max_height = get_max_height(time, worker_time)
                total_reduction += max_height
                if total_reduction >= mountainHeight:
                    return True
            return total_reduction >= mountainHeight
        
        def get_max_height(time, worker_time):
            # Solve: worker_time * x * (x + 1) / 2 <= time
            # x^2 + x <= 2 * time / worker_time
            limit = 2 * time // worker_time
            x = int(limit ** 0.5)
            
            # Check x and x+1 to find the exact answer
            while x * (x + 1) <= limit:
                x += 1
            while x * (x + 1) > limit:
                x -= 1
            
            return x
        
        left = 1
        right = mountainHeight * (mountainHeight + 1) // 2 * min(workerTimes)
        
        while left < right:
            mid = (left + right) // 2
            if can_finish(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public long MinNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        long left = 1;
        long right = (long)mountainHeight * (mountainHeight + 1) / 2 * workerTimes.Min();
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (CanFinish(mid, mountainHeight, workerTimes)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    private bool CanFinish(long time, int mountainHeight, int[] workerTimes) {
        long totalReduction = 0;
        foreach (int workerTime in workerTimes) {
            long maxHeight = GetMaxHeight(time, workerTime);
            totalReduction += maxHeight;
            if (totalReduction >= mountainHeight) {
                return true;
            }
        }
        return totalReduction >= mountainHeight;
    }
    
    private long GetMaxHeight(long time, int workerTime) {
        // Solve: workerTime * x * (x + 1) / 2 <= time
        // x^2 + x <= 2 * time / workerTime
        long limit = 2 * time / workerTime;
        long x = (long)Math.Sqrt(limit);
        
        // Check x and x+1 to find the exact answer
        while (x * (x + 1) <= limit) x++;
        while (x * (x + 1) > limit) x--;
        
        return x;
    }
}

var minNumberOfSeconds = function(mountainHeight, workerTimes) {
    function canFinish(time) {
        let totalReduction = 0;
        for (let workerTime of workerTimes) {
            let maxHeight = getMaxHeight(time, workerTime);
            totalReduction += maxHeight;
            if (totalReduction >= mountainHeight) {
                return true;
            }
        }
        return totalReduction >= mountainHeight;
    }
    
    function getMaxHeight(time, workerTime) {
        // Solve: workerTime * x * (x + 1) / 2 <= time
        // x^2 + x <= 2 * time / workerTime
        let limit = Math.floor(2 * time / workerTime);
        let x = Math.floor(Math.sqrt(limit));
        
        // Check x and x+1 to find the exact answer
        while (x * (x + 1) <= limit) x++;
        while (x * (x + 1) > limit) x--;
        
        return x;
    }
    
    let left = 1;
    let right = mountainHeight * (mountainHeight + 1) / 2 * Math.min(...workerTimes);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canFinish(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log(H²×T))n 为工人数量，H 为山峰高度，T 为最小工作时间
空间复杂度O(1)只使用常数额外空间