Medium

题目描述

有 n 个项目，编号从 0 到 n - 1。给定一个整数数组 milestones，其中 milestones[i] 表示第 i 个项目的里程碑数量。

你可以按照以下两个规则在项目上工作：

  • 每周，你将完成一个项目的一个里程碑。你必须每周都工作。
  • 你不能连续两周在同一个项目的里程碑上工作。

一旦所有项目的所有里程碑都完成，或者如果你只能在会违反上述规则的里程碑上工作，你将停止工作。注意，由于这些约束，你可能无法完成每个项目的里程碑。

返回在不违反上述规则的情况下，你能够在项目上工作的最大周数。

示例 1：

输入：milestones = [1,2,3]
输出：6
解释：一种可能的情况是：
- 第1周，你将在项目0的里程碑上工作。
- 第2周，你将在项目2的里程碑上工作。
- 第3周，你将在项目1的里程碑上工作。
- 第4周，你将在项目2的里程碑上工作。
- 第5周，你将在项目1的里程碑上工作。
- 第6周，你将在项目2的里程碑上工作。
总周数为6。

示例 2：

输入：milestones = [5,2,1]
输出：7
解释：一种可能的情况是：
- 第1周，你将在项目0的里程碑上工作。
- 第2周，你将在项目1的里程碑上工作。
- 第3周，你将在项目0的里程碑上工作。
- 第4周，你将在项目1的里程碑上工作。
- 第5周，你将在项目0的里程碑上工作。
- 第6周，你将在项目2的里程碑上工作。
- 第7周，你将在项目0的里程碑上工作。
总周数为7。
注意，你不能在第8周在项目0的最后一个里程碑上工作，因为这会违反规则。
因此，项目0中有一个里程碑将保持未完成状态。

约束条件：

  • n == milestones.length
  • 1 <= n <= 10^5
  • 1 <= milestones[i] <= 10^9

解题思路

这是一道贪心算法问题。核心思想是分析在不能连续工作同一项目的约束下，最多能工作多少周。

分析思路：

首先考虑理想情况：如果没有连续工作限制，我们可以工作的总周数就是所有里程碑的总和。但由于不能连续工作同一项目，我们需要分析什么情况下会受到限制。

关键观察：限制我们工作周数的主要因素是最大里程碑数的项目。如果某个项目的里程碑数过多，我们可能无法在其他项目之间穿插完成所有工作。

贪心策略：

设最大里程碑数为 maxMilestones，其余所有项目里程碑总和为 otherSum。

  • 如果 maxMilestones <= otherSum + 1，说明我们可以通过在最大项目和其他项目之间交替工作，完成所有里程碑。此时答案是所有里程碑的总和。

  • 如果 maxMilestones > otherSum + 1，说明最大项目的里程碑过多，我们最多只能工作 2 * otherSum + 1 周（在其他项目之间穿插最大项目的工作）。

推荐解法： 贪心算法，时间复杂度O(n)，空间复杂度O(1)，是最优解法。

代码实现

class Solution {
public:
    long long numberOfWeeks(vector<int>& milestones) {
        long long total = 0;
        long long maxMilestones = 0;
        
        for (int milestone : milestones) {
            total += milestone;
            maxMilestones = max(maxMilestones, (long long)milestone);
        }
        
        long long otherSum = total - maxMilestones;
        
        if (maxMilestones <= otherSum + 1) {
            return total;
        } else {
            return 2 * otherSum + 1;
        }
    }
};

class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        total = sum(milestones)
        max_milestones = max(milestones)
        other_sum = total - max_milestones
        
        if max_milestones <= other_sum + 1:
            return total
        else:
            return 2 * other_sum + 1

public class Solution {
    public long NumberOfWeeks(int[] milestones) {
        long total = 0;
        long maxMilestones = 0;
        
        foreach (int milestone in milestones) {
            total += milestone;
            maxMilestones = Math.Max(maxMilestones, milestone);
        }
        
        long otherSum = total - maxMilestones;
        
        if (maxMilestones <= otherSum + 1) {
            return total;
        } else {
            return 2 * otherSum + 1;
        }
    }
}

/**
 * @param {number[]} milestones
 * @return {number}
 */
var numberOfWeeks = function(milestones) {
    let total = 0;
    let maxMilestones = 0;
    
    for (let milestone of milestones) {
        total += milestone;
        maxMilestones = Math.max(maxMilestones, milestone);
    }
    
    let otherSum = total - maxMilestones;
    
    if (maxMilestones <= otherSum + 1) {
        return total;
    } else {
        return 2 * otherSum + 1;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次数组计算总和和最大值
空间复杂度O(1)只使用常数额外空间

相关题目