LeetCode 每日一题笔记

0. 前言

• 日期：2026.05.12
• 题目：1665. 完成所有任务的最少初始能量
• 难度：中等
• 标签：数组、贪心、排序

1. 题目理解

问题描述： 给定二维数组 tasks，其中 tasks[i] = [实际消耗, 最低要求]。 执行第 i 个任务必须满足：当前能量 ≥ 最低要求。 执行后能量会 减去实际消耗。 求完成所有任务需要的 最小初始能量。

示例：

输入：tasks = [[1,2],[2,4],[3,6],[4,8]] 输出：8

2. 解题思路

核心观察

• 贪心策略：按（最低要求 - 实际消耗）降序排序
• 先做“差值大”的任务，最后做“差值小”的任务，能让初始能量最小

算法步骤

1. 排序：按 (b - a) 从大到小排序任务
2. 先计算所有任务的总实际消耗（理论最低下限）
3. 模拟执行任务，若当前能量不够最低要求，补充差值
4. 最终得到最小初始能量

3. 代码实现

package lc1665;

import java.util.Arrays;

class Solution {
    public int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, (row1, row2) -> {
            return (row2[1] - row2[0]) - (row1[1] - row1[0]);
        });
        int res = 0;
        for (int i = 0; i < tasks.length; i++) {
            res += tasks[i][0];
        }
        int temp = res;
        for (int i = 0; i < tasks.length; i++) {
            if (temp >= tasks[i][1]) {
                temp -= tasks[i][0];
            } else {
                res += tasks[i][1] - temp;
                temp = tasks[i][1] - tasks[i][0];
            }
        }
        return res;
    }
}

4. 代码优化说明

• 贪心排序一次完成，无额外数据结构
• 仅两次遍历，无嵌套循环
• 空间 O(1) 额外空间，时间最优

5. 复杂度分析

• 时间复杂度：O(n log n) 排序主导复杂度
• 空间复杂度：O(1) 仅使用常数变量

6. 总结

• 贪心核心：按 (b - a) 降序排列
• 先算总消耗，再模拟补足不足
• 是任务门槛类贪心的经典模板题