当前位置：首页 > article >正文

贪心算法汇总

article 2025/1/13 5:33:53

1.贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

如何能看出局部最优是否能推出整体最优

靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。

如何验证可不可以用贪心算法

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

可有有同学认为手动模拟，举例子得出的结论不靠谱，想要严格的数学证明。

一般数学证明有如下两种方法：

数学归纳法
反证法

贪心算法一般分为如下四步：

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解

2.分发饼干

力扣题目链接(opens new window)

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1 解释:你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输出 1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释:你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2.

提示：

1 <= g.length <= 3 * 10^4
0 <= s.length <= 3 * 10^4
1 <= g[i], s[j] <= 2^31 - 1

public class Distribute_Cookies {
    public int findContentChildren1(int[] g, int[] s) {//接受两个整数数组 g 和 s 作为参数，分别表示孩子们的满足度和饼干的大小，返回能满足的孩子的最大数量。
        Arrays.sort(g);//对孩子们的满足度数组 g 进行升序排序。排序后，满足度低的孩子会排在前面，方便后续依次尝试为他们分配饼干。
        Arrays.sort(s);//对饼干的大小数组 s 进行升序排序。排序后，小的饼干会排在前面，优先满足满足度低的孩子。
        int start = 0;//用于跟踪 g 数组中当前考虑的孩子的索引，初始值为 0，表示从满足度最低的孩子开始考虑。
        int count = 0;//用于计数成功满足的孩子的数量，初始值为 0。
        for (int i = 0; i < s.length && start < g.length; i++) {//遍历饼干数组s，同时确保不超过g数组的长度。这个循环确保我们考虑每个饼干，并尝试找到一个满足度匹配或更高的孩子。
            if (s[i] >= g[start]) {//如果当前饼干的大小s[i]大于或等于当前孩子的满足度g[start]，则表示这个孩子可以被这个饼干满足。
                start++;//将 start 加 1，指向下一个孩子，准备为下一个孩子寻找合适的饼干。
                count++;//将满足的孩子数量加 1。
            }
        }
        return count;//循环结束后，count 中存储的就是能满足的孩子的最大数量，将其返回。
    }
}

假设 g = [1, 2, 3]，s = [1, 1]：

排序后，g = [1, 2, 3]，s = [1, 1]。
初始化 start = 0，count = 0。
进入 for 循环：
- 当 i = 0 时，s[0] = 1，g[0] = 1，s[0] >= g[0] 成立，start 变为 1，count 变为 1。
- 当 i = 1 时，s[1] = 1，g[1] = 2，s[1] < g[1] 不成立，不执行 start++ 和 count++。
循环结束，返回 count，即 1，表示最多能满足 1 个孩子。

再假设 g = [1, 2]，s = [1, 2, 3]：

排序后，g = [1, 2]，s = [1, 2, 3]。
初始化 start = 0，count = 0。
进入 for 循环：
- 当 i = 0 时，s[0] = 1，g[0] = 1，s[0] >= g[0] 成立，start 变为 1，count 变为 1。
- 当 i = 1 时，s[1] = 2，g[1] = 2，s[1] >= g[1] 成立，start 变为 2，count 变为 2。
循环结束，返回 count，即 2，表示最多能满足 2 个孩子。

通过这种方式，代码通过排序和遍历，有效地找出了最多能满足的孩子数量。

3.摆动序列

力扣题目链接(opens new window)

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。

示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

示例 3:

输入: [1,2,3,4,5,6,7,8,9]
输出: 2

public class Oscillating_Sequence {
    public int wiggleMaxLength1(int[] nums) {//接受一个整数数组 nums 作为参数，返回该数组中摆动序列的最大长度。
        if (nums.length <= 1) {//单个元素或空数组本身就是摆动序列。
            return nums.length;//如果数组 nums 的长度小于等于 1，那么这个数组本身就是一个摆动序列，直接返回数组的长度。
        }
        int curDiff = 0; //表示当前元素与前一个元素的差值，初始值为 0。
        int preDiff = 0;//表示前一个元素与前前一个元素的差值，初始值为 0。
        int count = 1;//表示摆动序列的长度，由于至少包含第一个元素，所以初始值为 1。
        for (int i = 1; i < nums.length; i++) {//从第二个元素开始遍历数组。
            curDiff = nums[i] - nums[i - 1];//计算当前元素与前一个元素的差值。
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {//检查当前差值和上一个差值的符号是否相反（一正一负），或者当前差值不为0而上一个差值为0（初始情况）。
                count++;//如果满足条件，将摆动序列的长度 count 加 1。
                preDiff = curDiff;//将当前差值赋值给上一个差值，为下一次迭代做准备。
            }
        }
        return count;//循环结束后，count 中存储的就是数组 nums 中摆动序列的最大长度，将其返回。
    }
}

假设输入数组 nums = [1, 7, 4, 9, 2, 5]：

初始化：curDiff = 0，preDiff = 0，count = 1。
第一次循环：i = 1，curDiff = 7 - 1 = 6，preDiff = 0，满足 curDiff > 0 && preDiff <= 0，count 变为 2，preDiff 变为 6。
第二次循环：i = 2，curDiff = 4 - 7 = -3，preDiff = 6，满足 curDiff < 0 && preDiff >= 0，count 变为 3，preDiff 变为 -3。
第三次循环：i = 3，curDiff = 9 - 4 = 5，preDiff = -3，满足 curDiff > 0 && preDiff <= 0，count 变为 4，preDiff 变为 5。
第四次循环：i = 4，curDiff = 2 - 9 = -7，preDiff = 5，满足 curDiff < 0 && preDiff >= 0，count 变为 5，preDiff 变为 -7。
第五次循环：i = 5，curDiff = 5 - 2 = 3，preDiff = -7，满足 curDiff > 0 && preDiff <= 0，count 变为 6，preDiff 变为 3。

最终返回 count，即 6，表示数组 [1, 7, 4, 9, 2, 5] 中摆动序列的最大长度是 6。

4.最大子序和

力扣题目链接(opens new window)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

public class Maximum_Subarray_Sum {
    public int maxSubArray1(int[] nums) {//接受一个整数数组nums作为参数，返回该数组中的最大子序和。
        if (nums.length == 1){//只有一个元素，那么最大子序和就是该元素本身，直接返回。
            return nums[0];
        }
        int sum = Integer.MIN_VALUE;//用于存储最大子序和，初始值设为Integer.MIN_VALUE，这样可以确保任何数组元素都比它大，方便后续更新最大子序和。
        int count = 0;//用于存储当前子序的和，初始值为0。
        for (int i = 0; i < nums.length; i++){//从数组的第一个元素（索引为 0）开始遍历到最后一个元素。
            count += nums[i];//将当前元素加到当前子序和中，不断累加以计算包含当前元素的子序和。
            sum = Math.max(sum, count);//如果当前子序和大于已知的最大子序和，则更新最大子序和。
            if (count <= 0){//如果当前子序和小于等于0，说明继续累加只会使和更小，因此重置当前子序和为0，从下一个元素开始新的子序。
                count = 0;
            }
        }
        return sum;//循环结束后，sum中存储的就是数组nums中的最大子序和，将其返回。
    }
}

假设输入数组nums = [-2, 1, -3, 4, -1, 2, 5, -3]：

初始化：sum = Integer.MIN_VALUE，count = 0。
第一次循环：i = 0，count = count + (-2) = -2，sum = Math.max(Integer.MIN_VALUE, -2) = -2，因为count = -2 <= 0，所以count = 0。
第二次循环：i = 1，count = count + 1 = 1，sum = Math.max(-2, 1) = 1，count = 1 > 0，count保持为 1。
第三次循环：i = 2，count = 1 + (-3) = -2，sum = Math.max(1, -2) = 1，因为count = -2 <= 0，所以count = 0。
第四次循环：i = 3，count = 0 + 4 = 4，sum = Math.max(1, 4) = 4，count = 4 > 0，count保持为 4。
第五次循环：i = 4，count = 4 + (-1) = 3，sum = Math.max(4, 3) = 4，count = 3 > 0，count保持为 3。
第六次循环：i = 5，count = 3 + 2 = 5，sum = Math.max(4, 5) = 5，count = 5 > 0，count保持为 5。
第七次循环：i = 6，count = 5 + 5 = 10，sum = Math.max(5, 10) = 10，count = 10 > 0，count保持为 10。
第八次循环：i = 7，count = 10 + (-3) = 7，sum = Math.max(10, 7) = 10，count由于大于 0 保持不变。

最终返回sum，即 10，这就是数组[-2, 1, -3, 4, -1, 2, 5, -3]中的最大子序和。

5.买卖股票的最佳时机 II

力扣题目链接(opens new window)

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

public class The_Best_Time_to_Buy_and_Sell_StocksII {
    public int maxProfit1(int[] prices) {//接受一个整数数组prices作为参数，该数组表示每天的股票价格，返回在这些价格序列下进行多次买卖所能获得的最大利润。
        int result = 0;//用于累积所有交易的总利润，初始值为 0。
        for (int i = 1; i < prices.length; i++) {//从数组的第二个元素（索引为 1）开始遍历到最后一个元素。这是因为我们需要比较当前天的价格（prices[i]）和前一天的价格（prices[i - 1]），所以i从 1 开始。
            result += Math.max(prices[i] - prices[i - 1], 0);//计算当前天的股票价格与前一天的股票价格之差，这个差值表示如果在第i - 1天买入，在第i天卖出所能获得的利润。并使用Math.max函数来确保这个差值不会是负数。如果差值是正数，表示卖出价格高于买入价格，说明第i天的价格高于第i - 1天的价格，在这种情况下，进行一次买卖可以获得利润，就将这个利润值累加到result中；如果差值是负数，表示卖出价格低于买入价格，进行这次买卖会亏损，为了保证总利润不减少，这里取 0，即不进行这次买卖。每次循环都会将这个计算得到的利润（或者 0）加到result变量上，从而不断累积总利润。
        }
        return result;//循环结束后，result中存储的就是在给定的股票价格序列下进行多次买卖所能获得的最大利润，将其返回。
    }
}

假设输入数组prices = [7, 1, 5, 3, 6, 4]：

第一次循环：i = 1，prices[1] - prices[0] = 1 - 7 = -6，Math.max(-6, 0) = 0，result = 0 + 0 = 0。
第二次循环：i = 2，prices[2] - prices[1] = 5 - 1 = 4，Math.max(4, 0) = 4，result = 0 + 4 = 4。
第三次循环：i = 3，prices[3] - prices[2] = 3 - 5 = -2，Math.max(-2, 0) = 0，result = 4 + 0 = 4。
第四次循环：i = 4，prices[4] - prices[3] = 6 - 3 = 3，Math.max(3, 0) = 3，result = 4 + 3 = 7。
第五次循环：i = 5，prices[5] - prices[4] = 4 - 6 = -2，Math.max(-2, 0) = 0，result = 7 + 0 = 7。

最终返回result，即 7，这就是在股票价格序列[7, 1, 5, 3, 6, 4]下进行多次买卖所能获得的最大利润。这种方法的核心思想是只要当天价格比前一天高，就进行一次买卖，通过不断累加这些小的利润来获得最大总利润。

6.跳跃游戏

力扣题目链接(opens new window)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，所以你永远不可能到达最后一个位置。

public class Jump_Game {
    public boolean canJump(int[] nums) {//接受一个整数数组 nums 作为参数，返回一个布尔值，表示是否能够通过跳跃到达数组的末尾。
        if (nums.length == 1) {//数组只有一个元素，那么不需要跳跃，直接返回true。
            return true;
        }
        int coverRange = 0;//存储当前能够到达的最远位置。初始值为 0，表示从数组的第一个位置开始。
        for (int i = 0; i <= coverRange; i++) {//从数组的第一个元素开始遍历，只要当前索引 i 不超过当前能够到达的最远位置 coverRange，就继续循环。
            coverRange = Math.max(coverRange, i + nums[i]);//对于每个索引 i，i + nums[i] 表示从当前位置 i 出发，最多能够跳跃到的位置。通过 Math.max 函数，取 coverRange 和 i + nums[i] 中的较大值，更新 coverRange，即当前能够到达的最远位置。
            if (coverRange >= nums.length - 1) {//每次更新 coverRange 后，检查 coverRange 是否大于或等于数组的最后一个元素的索引（nums.length - 1）。如果是，说明可以通过跳跃到达数组的末尾，直接返回 true。
                return true;
            }
        }
        return false;//如果 for 循环结束后，仍然没有满足 coverRange >= nums.length - 1 的条件，说明无法通过跳跃到达数组的末尾，返回 false。
    }

}

假设输入数组 nums = [2, 3, 1, 1, 4]：

初始化：coverRange = 0。
第一次循环：i = 0，i + nums[i] = 0 + 2 = 2，coverRange = Math.max(0, 2) = 2。此时 coverRange < nums.length - 1，继续循环。
第二次循环：i = 1，i + nums[i] = 1 + 3 = 4，coverRange = Math.max(2, 4) = 4。此时 coverRange >= nums.length - 1（因为 nums.length - 1 = 4），返回 true。

再假设输入数组 nums = [3, 2, 1, 0, 4]：

初始化：coverRange = 0。
第一次循环：i = 0，i + nums[i] = 0 + 3 = 3，coverRange = Math.max(0, 3) = 3。此时 coverRange < nums.length - 1，继续循环。
第二次循环：i = 1，i + nums[i] = 1 + 2 = 3，coverRange = Math.max(3, 3) = 3。
第三次循环：i = 2，i + nums[i] = 2 + 1 = 3，coverRange = Math.max(3, 3) = 3。
第四次循环：i = 3，i + nums[i] = 3 + 0 = 3，coverRange = Math.max(3, 3) = 3。此时 coverRange < nums.length - 1，循环结束。
最终返回 false，因为无法到达数组末尾。

通过这种方式，代码能够有效地判断在给定的跳跃规则下是否能够到达数组的末尾。

7.跳跃游戏 II

力扣题目链接(opens new window)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明: 假设你总是可以到达数组的最后一个位置。

public class Jump_GameII {
    public int jump2(int[] nums) {//接受一个整数数组 nums 作为参数，返回从数组第一个元素跳到最后一个元素所需的最少跳跃次数。
        int result = 0;//用来记录跳跃的次数。
        int end = 0; // 当前覆盖的最远距离下标
        int temp = 0; // 下一步覆盖的最远距离下标
        for (int i = 0; i <= end && end < nums.length - 1; ++i) {//循环会在到达最远位置或者到达数组末尾时停止。for 循环的条件是 i <= end && end < nums.length - 1。i <= end 确保当前遍历的位置 i 在当前能够覆盖的范围内，end < nums.length - 1 表示当前覆盖的最远距离还没有到达数组的末尾。只要这两个条件都满足，循环就会继续执行。
            temp = Math.max(temp, i + nums[i]);//对于每个索引 i，i + nums[i] 表示从当前位置 i 出发，最多能够跳跃到的位置。通过 Math.max 函数，取 temp 和 i + nums[i] 中的较大值，更新 temp，即记录下一步可能覆盖的最远距离下标。
            if (i == end) {//当 i 等于 end 时，说明已经走到了当前步骤能够到达的最远位置。此时，将 end 更新为 temp，即更新当前覆盖的最远距离下标。同时，将跳跃次数 result 加 1，表示进行了一次新的跳跃。
                end = temp;
                result++;
            }
        }
        return result;//循环结束后，result 中存储的就是从数组第一个元素跳到最后一个元素所需的最少跳跃次数，将其返回。
    }
}

假设输入数组 nums = [2, 3, 1, 1, 4]：

初始化：result = 0，end = 0，temp = 0。
第一次循环：i = 0，i + nums[i] = 0 + 2 = 2，temp = Math.max(0, 2) = 2。此时 i == end 成立，end = temp = 2，result = 1。
第二次循环：i = 1，i + nums[i] = 1 + 3 = 4，temp = Math.max(2, 4) = 4。此时 i!= end，不执行更新 end 和 result 的操作。
第三次循环：i = 2，i + nums[i] = 2 + 1 = 3，temp = Math.max(4, 3) = 4。此时 i == end 成立，end = temp = 4，result = 2。
循环结束，因为 end >= nums.length - 1，返回 result，即 2。这表示从数组第一个元素跳到最后一个元素最少需要跳跃 2 次。

8.K次取反后最大化的数组和

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）

以这种方式修改数组后，返回数组可能的最大和。

示例 1：

输入：A = [4,2,3], K = 1
输出：5
解释：选择索引 (1) ，然后 A 变为 [4,-2,3]。

示例 2：

输入：A = [3,-1,0,2], K = 3
输出：6
解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。

示例 3：

输入：A = [2,-3,-1,5,-4], K = 2
输出：13
解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。

提示：

1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100

public class Maximum_Sum_of_Array_After_K_Negations {
    public int largestSumAfterKNegations2(int[] nums, int k) {//接受一个整数数组 nums 和一个整数 k 作为参数，k 表示可以对数组元素进行取反操作的次数。方法返回经过 k 次取反操作后数组的最大和。
        if (nums.length == 1) return nums[0];//如果数组只有一个元素，那么不需要进行任何取反操作，直接返回该元素作为最大和。
        Arrays.sort(nums);//对数组 nums 进行升序排序。这样做的目的是将数组中的负数排在前面，因为对负数进行取反操作可以使数组的和增大。
        for (int i = 0; i < nums.length && k > 0; i++) {//检查k是否大于0，即是否还有取反操作的机会。for 循环用于遍历数组 nums，同时检查是否还有剩余的取反操作次数（k > 0）。
            if (nums[i] < 0) {//检查当前元素是否为负数。如果是，那么将当前元素取反（负数变正数），并将k减1。
                nums[i] = -nums[i];
                k--;
            }
        }
        if (k % 2 == 1) {//循环结束后，如果k是奇数，这意味着我们还需要进行一次取反操作。这行代码再次对数组进行排序，以便找到最小的元素（可能是负数或正数），然后将其取反，以最大化数组的和。这是因为对最小的元素取反（无论它是正数还是负数），对总和的影响最小，从而可以保证最终的和是最大的。
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        int sum = 0;//初始化一个变量 sum 为 0，用于存储数组的和。
        for (int num : nums) {//使用增强型 for 循环遍历数组 nums，将每个元素累加到 sum 中。
            sum += num;
        }
        return sum;//最后返回 sum，即经过 k 次取反操作后数组的最大和。
    }
}

假设输入数组 nums = [-4, -2, -3]，k = 4：

首先，数组只有一个元素的情况不满足，继续执行。
对数组进行排序，nums 变为 [-4, -3, -2]。
进入 for 循环：
- 当 i = 0 时，nums[0] = -4 < 0，nums[0] = -(-4) = 4，k = 4 - 1 = 3。
- 当 i = 1 时，nums[1] = -3 < 0，nums[1] = -(-3) = 3，k = 3 - 1 = 2。
- 当 i = 2 时，nums[2] = -2 < 0，nums[2] = -(-2) = 2，k = 2 - 1 = 1。
for 循环结束后，k = 1，k % 2 == 1 成立。
再次对数组进行排序，nums 变为 [2, 3, 4]。
将 nums[0] 取反，nums[0] = -2，此时 nums 变为 [-2, 3, 4]。
计算数组的和：sum = -2 + 3 + 4 = 5，返回 5。

通过以上步骤，代码能够有效地计算出经过 k 次取反操作后数组的最大和。

9. 加油站

力扣题目链接(opens new window)

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。

示例 1: 输入:

gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3 解释:

从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2: 输入:

gas = [2,3,4]
cost = [3,4,3]
输出: -1
解释: 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。我们从 2 号加油站出发，可以获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油。开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油。开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油。你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。因此，无论怎样，你都不可能绕环路行驶一周。

环形数组就是一种特殊的数据结构概念，它在逻辑上可以看作是一个首尾相连的数组。例如，对于一个长度为 n 的环形数组，当访问索引 n 时，实际上会回到索引 0 的位置；访问索引 n + 1 时，会对应到索引 1 的位置。

(i + 1) % gas.length 这一操作就是用于实现环形数组索引的关键。

当 i + 1 未超过数组长度时：
假设 gas.length 为 5，当 i = 2 时，i + 1 = 3，此时 (i + 1) % gas.length = 3 % 5 = 3，这个结果就是正常的下一个索引位置，符合我们在普通数组中访问下一个元素的逻辑。
当 i + 1 超过数组长度时：

对于一个长度为 5 的数组，有效的索引是 0、1、2、3、4。

当 i = 4 时，i + 1 = 5，这个 5 在常规数组索引的语境下是超过了有效范围的。

同样假设 gas.length 为 5，当 i = 4 时，i + 1 = 5，而 (i + 1) % gas.length = 5 % 5 = 0。这里通过取模运算，使得索引回到了数组的开头，实现了环形数组的特性。

当 curSum < 0 时，需要将起点索引 index 更新为下一个加油站的索引。由于是环形路线，当 i 已经是数组的最后一个元素（即 i = gas.length - 1）时，下一个加油站的索引应该是 0。通过 (i + 1) % gas.length 这种取模运算，无论 i 处于什么位置，都能正确地计算出下一个加油站在环形数组中的索引，确保程序能够正确地遍历整个环形路线来寻找合适的起点。

public class gas_station {
    public int canCompleteCircuit2(int[] gas, int[] cost) {//接受两个整数数组gas和cost作为参数，分别表示每个加油站的汽油量和从该加油站到下一个加油站的消耗量。方法返回能够完成环形路线的起点索引，如果不存在则返回 - 1。
        int curSum = 0;//用于记录当前起点开始的累计油量差（油量减去消耗量）。
        int totalSum = 0;//用于记录整个环形路线上的总油量差。
        int index = 0;//用于记录当前的起点索引。
        for (int i = 0; i < gas.length; i++) {//在for循环中，对于每个加油站i，计算从该加油站获得的汽油量gas[i]减去行驶到下一个加油站的消耗量cost[i]，并将结果累加到curSum和totalSum中。curSum表示从当前假设的起点开始到当前加油站的累计油量差，totalSum表示整个环形路线的总油量差。
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {//如果 curSum 小于0，说明从当前起点开始的油量不足以到达下一个加油站，此时，需要更换起点。
                index = (i + 1) % gas.length ;//更新起点索引 index 为下一个加油站，使用取模运算(i + 1) % gas.length是为了确保索引在环形数组的范围内（即如果i + 1超过了数组的长度，会回到数组的开头）。。
                curSum = 0;//将curSum重置为 0，因为从新的起点开始重新计算累计油量差。
            }
        }
        if (totalSum < 0) return -1;//如果totalSum小于 0，说明整个环形路线上的总汽油量小于总消耗量，无论从哪个起点出发，汽车都无法完成一圈的行驶，因此返回 - 1。
        return index;//如果totalSum大于或等于 0，说明至少存在一个起点可以让汽车完成整个环形路线。此时，index记录的就是这样一个起点的索引，将其返回。
    }
}

假设gas = [1, 2, 3, 4, 5]，cost = [3, 4, 5, 1, 2]：

初始化：curSum = 0，totalSum = 0，index = 0。
第一次循环：i = 0，curSum = 1 - 3 = -2，totalSum = -2。因为curSum < 0，index = (0 + 1) % 5 = 1，curSum = 0。
第二次循环：i = 1，curSum = 2 - 4 = -2，totalSum = -2 + (-2) = -4。因为curSum < 0，index = (1 + 1) % 5 = 2，curSum = 0。
第三次循环：i = 2，curSum = 3 - 5 = -2，totalSum = -4 + (-2) = -6。因为curSum < 0，index = (2 + 1) % 5 = 3，curSum = 0。
第四次循环：i = 3，curSum = 4 - 1 = 3，totalSum = -6 + 3 = -3。curSum > 0，继续循环。
第五次循环：i = 4，curSum = 5 - 2 = 3，totalSum = -3 + 3 = 0。
循环结束，totalSum = 0，不小于 0，返回index，即3。这表示从索引为 3 的加油站出发，可以完成环形路线。

通过这种方式，代码有效地判断了是否存在能够完成环形路线的起点，并找到了这个起点的索引。

10.分发糖果

力扣题目链接(opens new window)

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

public class distribute_candies {
    public int candy(int[] ratings) {//接受一个整数数组 ratings 作为参数，该数组表示每个孩子的评分。方法返回分配给所有孩子的糖果总数。
        int len = ratings.length;//len 变量存储数组 ratings 的长度。
        int[] candyVec = new int[len];//整数数组，用于存储每个孩子应该获得的糖果数量，初始长度与 ratings 相同。
        candyVec[0] = 1;//第一个孩子至少获得 1 个糖果。
        for (int i = 1; i < len; i++) {//从第二个孩子开始遍历到数组的末尾。对于每个孩子 i，如果他们的评分 ratings[i] 高于前一个孩子 ratings[i - 1]，那么这个孩子将获得比前一个孩子多 1 个糖果，即 candyVec[i - 1] + 1；否则，这个孩子至少获得 1 个糖果。
            candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
        }
        for (int i = len - 2; i >= 0; i--) {//从倒数第二个孩子开始遍历到第一个孩子。对于每个孩子，如果他们的评分高于后一个孩子，他们将获得至少比后一个孩子多一个糖果，以确保后一个孩子不能偷走超过一半的糖果。
            if (ratings[i] > ratings[i + 1]) {//Math.max 函数是为了确保在更新 candyVec[i] 时，不会破坏之前从左到右遍历所确定的糖果数量关系。例如，如果之前从左到右遍历确定 candyVec[i] 已经比较大了，而从右到左遍历时需要根据当前条件调整 candyVec[i]，那么取两者中的较大值，以满足所有的条件。
                candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        int ans = 0;//将每个孩子获得的糖果数量累加到 ans 变量中。
        for (int num : candyVec) {//使用增强型 for 循环遍历 candyVec 数组，将每个孩子获得的糖果数量累加到 ans 中。
            ans += num;
        }
        return ans;//最后返回 ans，即分配给所有孩子的糖果总数。
    }
}

假设输入数组 ratings = [1, 2, 2]：

初始化：len = 3，candyVec = [1,?,?]。
第一次遍历（从左到右）：
- 当 i = 1 时，ratings[1] = 2 > ratings[0] = 1，所以 candyVec[1] = candyVec[0] + 1 = 2。
- 当 i = 2 时，ratings[2] = 2 == ratings[1] = 2，所以 candyVec[2] = 1。此时 candyVec = [1, 2, 1]。
第二次遍历（从右到左）：
- 当 i = 1 时，ratings[1] = 2 > ratings[2] = 2 不成立，不更新 candyVec[1]。
- 当 i = 0 时，ratings[0] = 1 < ratings[1] = 2 不成立，不更新 candyVec[0]。此时 candyVec 仍然是 [1, 2, 1]。
计算总糖果数：ans = 1 + 2 + 1 = 4，返回 4。

再假设输入数组 ratings = [1, 3, 2, 2, 1]：

初始化：len = 5，candyVec = [1,?,?]。
第一次遍历（从左到右）：
- 当 i = 1 时，ratings[1] = 3 > ratings[0] = 1，所以 candyVec[1] = candyVec[0] + 1 = 2。
- 当 i = 2 时，ratings[2] = 2 < ratings[1] = 3，所以 candyVec[2] = 1。
- 当 i = 3 时，ratings[3] = 2 == ratings[2] = 2，所以 candyVec[3] = 1。
- 当 i = 4 时，ratings[4] = 1 < ratings[3] = 2，所以 candyVec[4] = 1。此时 candyVec = [1, 2, 1, 1, 1]。
第二次遍历（从右到左）：
- 当 i = 3 时，ratings[3] = 2 > ratings[4] = 1，所以 candyVec[3] = Math.max(candyVec[3], candyVec[4] + 1) = 2。
- 当 i = 2 时，ratings[2] = 2 == ratings[3] = 2 不更新 candyVec[2]。
- 当 i = 1 时，ratings[1] = 3 > ratings[2] = 2，所以 candyVec[1] = Math.max(candyVec[1], candyVec[2] + 1) = 3。
- 当 i = 0 时，ratings[0] = 1 < ratings[1] = 3 不更新 candyVec[0]。此时 candyVec = [1, 3, 1, 2, 1]。
计算总糖果数：ans = 1 + 3 + 1 + 2 + 1 = 8，返回 8。

11.柠檬水找零

力扣题目链接(opens new window)

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：[5,5,5,10,20]
输出：true
解释：
- 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
- 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
- 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
- 由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

输入：[5,5,10]
输出：true

示例 3：

输入：[10,10]
输出：false

示例 4：

输入：[5,5,10,10,20]
输出：false
解释：
- 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
- 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
- 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
- 由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

0 <= bills.length <= 10000
bills[i] 不是 5 就是 10 或是 20

public class Lemonade_Change {
    public boolean lemonadeChange(int[] bills) {//接受一个整数数组 bills 作为参数，该数组表示顾客支付的一系列钞票面额。方法返回一个布尔值，true 表示可以给所有顾客正确找零，false 表示无法完成所有顾客的找零。
        int five = 0, ten = 0;//用于记录5元钞票的数量,用于记录10元钞票的数量。
        for (int bill : bills) {//循环会遍历每一个顾客支付的钞票，对每张钞票进行相应的找零处理。
            if (bill == 5) {//如果 bill 的值为 5，说明顾客支付了一张 5 元钞票。此时，将 five 变量的值加 1，表示我们现在拥有的 5 元钞票数量增加了一张。因为收到 5 元钞票不需要找零，直接增加 5 元钞票的储备。
                five++;
            } else if (bill == 10) {//当 bill 的值为 10 时，说明顾客支付了一张 10 元钞票。由于柠檬水售价假设为 5 元，需要找零 5 元。
                if (five == 0) {//首先检查 five 是否为 0，如果 five 为 0，即没有 5 元钞票用于找零，那么无法完成这次找零，直接返回 false。
                    return false;
                }//如果有 5 元钞票（five > 0），则将 five 的值减 1，表示用掉了一张 5 元钞票用于找零，同时将 ten 的值加 1，表示收到了一张 10 元钞票。
                five--;
                ten++;
            } else {//如果顾客支付的是20元钞票，有两种情况可以找零：如果有一张10元钞票和至少一张5元钞票，减少一张10元钞票和一张5元钞票。如果没有10元钞票，但至少有三张5元钞票，减少三张5元钞票。如果以上两种情况都不满足，返回 false 表示无法完成找零。
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;//如果整个 for 循环顺利结束，没有因为无法找零而返回 false，说明可以给所有顾客正确找零，此时返回 true。
    }
}

假设输入 bills = [5, 5, 10, 20]：

当 bill = 5 时，five 变为 1，ten 为 0。
当 bill = 5 时，five 变为 2，ten 为 0。
当 bill = 10 时，five 变为 1，ten 变为 1。
当 bill = 20 时，因为有一张 10 元钞票和一张 5 元钞票，five 变为 0，ten 变为 0。
循环结束，返回 true。

假设输入 bills = [5, 5, 10, 10, 20]：

当 bill = 5 时，five 变为 1，ten 为 0。
当 bill = 5 时，five 变为 2，ten 为 0。
当 bill = 10 时，five 变为 1，ten 变为 1。
当 bill = 10 时，five 变为 0，ten 变为 2。
当 bill = 20 时，既没有一张 10 元钞票和一张 5 元钞票的组合，也没有三张 5 元钞票，返回 false。

12.根据身高重建队列

力扣题目链接(opens new window)

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
- 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
- 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
- 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
- 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
- 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
- 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
- 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

1 <= people.length <= 2000
0 <= hi <= 10^6
0 <= ki < people.length

题目数据确保队列可以被重建

public class Reconstruct_Queue_by_Height {//接受一个二维整数数组 people 作为参数，其中每个元素 people[i] 是一个包含两个整数的数组，people[i][0] 表示第 i 个人的身高，people[i][1] 表示第 i 个人在队列中的相对位置（即前面有多少个身高大于或等于他的人）。方法返回一个重建后的二维数组，表示正确的队列顺序。
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {//Arrays.sort方法对people数组进行排序。这里使用了lambda表达式来定义比较器。在比较器中，如果两个人的身高相同（a[0] == b[0]），则根据他们的相对位置（a[1]和b[1]）进行升序排序。这是因为身高相同的人，相对位置小的应该排在前面。如果两个人的身高不同，则根据身高进行降序排序。这是因为身高较高的人会影响到身高较低的人的相对位置，先排身高高的人可以方便后续按照相对位置进行插入操作。
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });
        LinkedList<int[]> que = new LinkedList<>();//用于存储重建后的队列。
        for (int[] p : people) {//循环遍历排序后的 people 数组。对于数组中的每一个人 p，使用 que.add(p[1], p) 将其插入到 LinkedList 的指定位置 p[1]。这里的 p[1] 就是该人在队列中的相对位置，通过这种方式，能够保证每个人都被正确地插入到队列中，使得前面有 p[1] 个身高大于或等于他的人。
            que.add(p[1],p);
        }
        return que.toArray(new int[people.length][]);//将链表转换回二维数组，并返回。
    }
}

假设输入的 people 数组为 [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]：

排序后：
根据排序规则，数组会被排序为 [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]。
重建队列过程：
- 对于 [7,0]，插入到位置 0，此时队列为 [[7,0]]。
- 对于 [7,1]，插入到位置 1，此时队列为 [[7,0], [7,1]]。
- 对于 [6,1]，插入到位置 1，此时队列为 [[7,0], [6,1], [7,1]]。
- 对于 [5,0]，插入到位置 0，此时队列为 [[5,0], [7,0], [6,1], [7,1]]。
- 对于 [5,2]，插入到位置 2，此时队列为 [[5,0], [7,0], [5,2], [6,1], [7,1]]。
- 对于 [4,4]，插入到位置 4，此时队列为 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]。

最终返回的重建后的队列就是 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]。通过这种排序和插入的方式，成功地重建了符合要求的队列。

13.用最少数量的箭引爆气球

力扣题目链接(opens new window)

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2

示例 4：

输入：points = [[1,2]]
输出：1

示例 5：

输入：points = [[2,3],[2,3]]
输出：1

提示：

0 <= points.length <= 10^4
points[i].length == 2
-2^31 <= xstart < xend <= 2^31 - 1

public class Use_the_minimum_number_of_arrows_to_pop_balloons {
    public int findMinArrowShots(int[][] points) {//接受一个二维整数数组 points 作为参数，points 中的每个元素是一个包含两个整数的数组，分别表示一个气球的开始坐标和结束坐标。方法返回引爆所有气球所需的最少箭数。
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));//对输入的points数组进行排序。points是一个二维整数数组，其中每个元素是一个包含两个整数的数组，分别代表气球的开始坐标和结束坐标。这里使用Integer.compare方法根据气球的开始坐标进行升序排序。表示按照气球的开始坐标 a[0] 和 b[0] 进行升序排序。这样排序后，数组中前面的气球开始坐标总是小于或等于后面气球的开始坐标，方便后续处理重叠的气球。
        int count = 1;//初始化一个计数器count，用于记录需要的最少箭数。因为至少需要一支箭来引爆至少一个气球，所以初始值为1。
        for (int i = 1; i < points.length; i++) {//从第二个气球开始遍历排序后的points数组。第一个气球已经默认用了一支箭，所以从第二个气球开始检查与前一个气球的关系。
            if (points[i][0] > points[i - 1][1]) {//检查当前气球（points[i]）是否与前一个气球（points[i - 1]）相邻。如果不相邻（即当前气球的开始坐标大于前一个气球的结束坐标），则需要额外的一支箭来引爆当前气球，因此count加1。
                count++;
            } else {
                points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 如果当前气球与前一个气球相邻（即有重叠部分），则更新当前气球的结束坐标为两者结束坐标的较小值。这是因为一支箭可以同时引爆这两个气球，所以需要更新结束坐标以反映合并后的气球的结束位置，以便后续继续检查与其他气球的重叠情况。
            }
        }
        return count;//遍历完所有气球后，count 中存储的就是引爆所有气球所需的最少箭数，将其返回。
    }
}

假设输入的 points 数组为 [[10,16], [2,8], [1,6], [7,12]]：

排序后：
数组排序后变为 [[1,6], [2,8], [7,12], [10,16]]。
遍历过程：
- 当 i = 1 时，points[1][0] = 2，points[0][1] = 6，因为 2 <= 6，说明这两个气球有重叠部分。更新 points[1][1] = Math.min(8, 6) = 6。此时 count = 1。
- 当 i = 2 时，points[2][0] = 7，points[1][1] = 6，因为 7 > 6，这两个气球不相邻，需要额外一支箭，count++，count 变为 2。
- 当 i = 3 时，points[3][0] = 10，points[2][1] = 12，因为 10 <= 12，这两个气球有重叠部分。更新 points[3][1] = Math.min(16, 12) = 12。此时 count = 2。
最终结果：
遍历结束后，返回 count，即 2，表示引爆所有气球最少需要 2 支箭。

通过这种排序和遍历的方式，代码能够有效地计算出引爆所有气球所需的最少箭数。

14.无重叠区间

力扣题目链接(opens new window)

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

public class Non_overlapping_Intervals {
    public int eraseOverlapIntervals1(int[][] intervals) {//接受一个二维整数数组 intervals 作为参数，intervals 中的每个元素是一个包含两个整数的数组，分别表示区间的开始和结束坐标。方法返回需要移除的区间数量，以使剩下的区间互不重叠。
        Arrays.sort(intervals, (a, b)-> {
            return Integer.compare(a[0],b[0]);
        });//使用 Arrays.sort 方法对 intervals 数组进行排序。这里通过 lambda 表达式定义了比较器，Integer.compare(a[0], b[0]) 按照区间的开始坐标 a[0] 和 b[0] 进行升序排序。这样排序后，数组中前面的区间开始坐标总是小于或等于后面区间的开始坐标，方便后续处理重叠区间。
        int count = 1;//记录可以选择的不重叠区间的数量。初始值为1，因为至少可以选择第一个区间。
        for(int i = 1;i < intervals.length;i++){//从第二个区间（索引为 1）开始遍历排序后的 intervals 数组。因为第一个区间已经默认被选择，所以从第二个区间开始检查与前一个区间的重叠情况。
            if(intervals[i][0] < intervals[i-1][1]){//检查当前区间 intervals[i] 的开始坐标是否小于前一个区间 intervals[i - 1] 的结束坐标。如果是，说明这两个区间重叠。
                intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);//在重叠的情况下，更新当前区间的结束坐标为当前区间和前一个区间结束坐标中的较小值。这是因为我们希望保留一个较短的区间，以减少后续区间重叠的可能性。然后使用 continue 跳过当前循环，继续检查下一个区间，因为当前区间与前一个区间重叠，不能同时被选择。
                continue;
            }else{//如果当前区间的开始坐标大于或等于前一个区间的结束坐标，说明这两个区间不重叠。此时，将 count 加 1，表示又找到了一个可以选择的不重叠区间。
                count++;
            }
        }
        return intervals.length - count;//遍历完所有区间后，count 中存储的是可以选择的不重叠区间的数量。用总区间数 intervals.length 减去 count，就得到了需要移除的区间数量，以保证剩下的区间互不重叠。
    }
}

假设输入的 intervals 数组为 [[1,2], [2,3], [3,4], [1,3]]：

排序后：
数组排序后变为 [[1,2], [1,3], [2,3], [3,4]]。
遍历过程：
- 当 i = 1 时，intervals[1][0] = 1，intervals[0][1] = 2，因为 1 < 2，这两个区间重叠。更新 intervals[1][1] = Math.min(2, 3) = 2，然后 continue，继续下一次循环。此时 count = 1。
- 当 i = 2 时，intervals[2][0] = 2，intervals[1][1] = 2，因为 2 >= 2，这两个区间不重叠，count++，count 变为 2。
- 当 i = 3 时，intervals[3][0] = 3，intervals[2][1] = 3，因为 3 >= 3，这两个区间不重叠，count++，count 变为 3。
最终结果：
总区间数为 4，可以选择的不重叠区间数量为 3，所以返回 4 - 3 = 1，即需要移除 1 个区间才能使剩下的区间互不重叠。

通过这种排序和遍历的方式，代码能够有效地计算出需要移除的区间数量，以实现区间的不重叠。

15.划分字母区间

力扣题目链接(opens new window)

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8] 解释：划分结果为 "ababcbaca", "defegde", "hijhklij"。每个字母最多出现在一个片段中。像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。

public class Divide_the_Letter_Ranges {
    public List<Integer> partitionLabels1(String S) {//接受一个字符串 S 作为参数，返回一个包含每个划分区间长度的列表。
        List<Integer> list = new LinkedList<>();//存储最终的划分区间的长度。
        int[] edge = new int[26];//存储每个字母最后一次出现的位置。因为英文字母表有26个字母，所以数组大小为26。
        char[] chars = S.toCharArray();//将输入的字符串S转换为字符数组。
        for (int i = 0; i < chars.length; i++) {//遍历字符数组，使用字符的ASCII码减去'a'的ASCII码来作为索引，记录每个字母最后一次出现的索引位置。遍历字符数组 chars，对于每个字符 chars[i]，计算其对应的数组索引 chars[i] - 'a'，并将该字符最后一次出现的位置 i 记录在 edge 数组中。例如，如果字符是 'a'，则 'a' - 'a' = 0，edge[0] 将记录 'a' 在字符串中最后一次出现的位置。
            edge[chars[i] - 'a'] = i;
        }
        int idx = 0;//记录当前考察的区间的最右端边界。
        int last = -1;//记录当前划分区间的开始位置。
        for (int i = 0; i < chars.length; i++) {//for 循环中，对于每个字符 chars[i]
            idx = Math.max(idx,edge[chars[i] - 'a']);//对于当前遍历到的字符，更新idx为当前字符最后一次出现的位置和当前idx的最大值。这一步确保 idx 始终是当前考察区间内所有字符中最晚出现的位置。
            if (i == idx) {//如果当前索引i等于idx，则表示当前字符是构成区间的最后一个字符，因为它是当前考察区间内所有字符中最晚出现的。
                list.add(i - last);//将当前区间的长度（结束位置i减去开始位置last）添加到结果列表中。
                last = i;//更新last为当前索引i，为下一个区间做准备。
            }
        }
        return list;//返回包含每个划分区间长度的列表。
    }
}

假设输入字符串 S = "ababcbacadefegdehijhklij"：

计算每个字母最后一次出现的位置：
- 遍历字符串后，edge 数组记录了每个字母最后一次出现的位置。例如，'a' 最后一次出现在位置 8，'b' 最后一次出现在位置 5，等等。
划分区间过程：
- 初始化 idx = 0，last = -1。
- 当 i = 0，chars[0] = 'a'，idx = Math.max(0, edge['a' - 'a']) = 8。
- 当 i = 1，chars[1] = 'b'，idx = Math.max(8, edge['b' - 'a']) = 8。
- 当 i = 2，chars[2] = 'a'，idx = Math.max(8, edge['a' - 'a']) = 8。
- 当 i = 3，chars[3] = 'b'，idx = Math.max(8, edge['b' - 'a']) = 8。
- 当 i = 4，chars[4] = 'c'，idx = Math.max(8, edge['c' - 'a']) = 8。
- 当 i = 5，chars[5] = 'b'，idx = Math.max(8, edge['b' - 'a']) = 8。
- 当 i = 6，chars[6] = 'a'，idx = Math.max(8, edge['a' - 'a']) = 8。
- 当 i = 7，chars[7] = 'c'，idx = Math.max(8, edge['c' - 'a']) = 8。
- 当 i = 8，chars[8] = 'a'，i == idx，此时将 8 - (-1) = 9 添加到 list 中，last = 8。
- 后续继续遍历，依次计算其他区间长度并添加到 list 中。

最终，list 中存储了每个划分区间的长度，返回该列表。

16.合并区间

力扣题目链接(opens new window)

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。请重置默认代码定义以获取新方法签名。

public class Merge_Intervals {
    public int[][] merge2(int[][] intervals) {//接受一个二维整数数组 intervals 作为参数，返回合并后的区间数组。
        LinkedList<int[]> res = new LinkedList<>();//存储合并后的区间。使用 LinkedList 是因为在遍历过程中可能需要频繁地添加和删除元素，LinkedList 在这种情况下具有较好的性能。
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));//使用 Arrays.sort 方法对 intervals 数组进行排序。这里通过 lambda 表达式定义了比较器，Integer.compare(o1[0], o2[0]) 表示按照区间的左边界 o1[0] 和 o2[0] 进行升序排序。排序后，数组中前面的区间左边界总是小于或等于后面区间的左边界，方便后续合并重叠区间。
        res.add(intervals[0]);//将排序后的第一个区间 intervals[0] 添加到结果列表 res 中。这是因为第一个区间是合并过程的起始区间。
        for (int i = 1; i < intervals.length; i++) {//从第二个区间（索引为 1）开始遍历排序后的 intervals 数组。
            if (intervals[i][0] <= res.getLast()[1]) {//检查当前区间 intervals[i] 的左边界是否小于或等于结果列表 res 中最后一个区间的右边界。如果是，则说明这两个区间重叠。
                int start = res.getLast()[0];//如果区间重叠，获取结果列表中最后一个区间的左边界，因为合并后的区间左边界不变。
                int end = Math.max(intervals[i][1], res.getLast()[1]);//算合并后的区间右边界，取当前区间 intervals[i] 的右边界和结果列表中最后一个区间的右边界的较大值。
                res.removeLast();//从结果列表中移除最后一个区间，因为要将其与当前区间合并。
                res.add(new int[]{start, end});//将合并后的区间添加到结果列表中。
            }
            else {
                res.add(intervals[i]);//当区间不重叠，直接将当前区间 intervals[i] 添加到结果列表 res 中，因为它与结果列表中的最后一个区间不重叠，不需要合并。
            }
        }
        return res.toArray(new int[res.size()][]);//将结果列表转换为二维数组并返回。
    }

}

假设输入的 intervals 数组为 [[1,3], [2,6], [8,10], [15,18]]：

排序后：
数组排序后仍为 [[1,3], [2,6], [8,10], [15,18]]（因为原数组已经按左边界有序）。
遍历和合并过程：
- 初始化 res = [[1,3]]。
- 当 i = 1 时，intervals[1][0] = 2，res.getLast()[1] = 3，因为 2 <= 3，区间重叠。合并后的区间为 [1, 6]，此时 res = [[1,6]]。
- 当 i = 2 时，intervals[2][0] = 8，res.getLast()[1] = 6，因为 8 > 6，区间不重叠，将 [8,10] 添加到 res 中，此时 res = [[1,6], [8,10]]。
- 当 i = 3 时，intervals[3][0] = 15，res.getLast()[1] = 10，因为 15 > 10，区间不重叠，将 [15,18] 添加到 res 中，此时 res = [[1,6], [8,10], [15,18]]。
最终结果：
将 res 转换为二维数组并返回，结果为 [[1,6], [8,10], [15,18]]。

通过这种排序和遍历的方式，代码有效地实现了区间的合并功能。

17.单调递增的数字

力扣题目链接(opens new window)

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299

说明: N 是在 [0, 10^9] 范围内的一个整数。

public class monotonically_increasing_numbers {
    public int monotoneIncreasingDigits2(int n) {//接受一个整数n作为参数，并返回一个整数，该整数是小于或等于n的最大单调递增数字。
        String s = String.valueOf(n);//将整数n转换为字符串s，以便逐位处理。
        char[] chars = s.toCharArray();//将字符串s转换为字符数组chars，这样可以通过索引访问和修改每一位数字。
        int start = s.length();//初始化start变量为字符串的长度，这个变量将用于标记需要被修改的数字位的起始位置。
        for (int i = s.length() - 2; i >= 0; i--) {//从数组的倒数第二个元素开始向前遍历，检查每一位数字是否大于其后一位数字。
            if (chars[i] > chars[i + 1]) {//如果当前位数字大于其后一位数字，说明我们需要调整当前位数字以保持单调递增。我们将当前位数字减1，并更新start为当前位的索引。
                chars[i]--;
                start = i+1;//将 start 更新为 i + 1，这是因为从 i + 1 位置开始往后的所有数字都需要被设置为 9，以确保得到的数字是小于或等于原始数字 n 的最大单调递增数字。
            }
        }
        for (int i = start; i < s.length(); i++) {//从start位置开始，将所有后续的数字位设置为9，这是因为在调整了前面的数字后，为了保证得到的数字是最大的单调递增数字，后面的数字都应该取最大值 9。
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));//使用String.valueOf方法将字符数组重新组合成一个字符串，然后使用Integer.parseInt将其转换回整数。
    }
}

假设输入 n = 332：

将 n 转换为字符串 s = "332"，再转换为字符数组 chars = {'3', '3', '2'}。
初始化 start = 3。
进入第一个 for 循环：
- 当 i = 1 时，chars[1] = '3'，chars[2] = '2'，因为 3 > 2，所以 chars[1]--，chars[1] 变为 '2'，start = 2。
进入第二个 for 循环：
- 当 i = 2 时，chars[2] = '9'。
字符数组变为 {'3', '2', '9'}，转换为字符串 "329"，再转换为整数 329 并返回。

通过以上步骤，代码能够正确地找到小于或等于给定整数的最大单调递增数字。

18.监控二叉树

力扣题目链接(opens new window)

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1：

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

示例 2：

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。上图显示了摄像头放置的有效位置之一。

提示：

给定树的节点数的范围是 [1, 1000]。
每个节点的值都是 0。

public class Binary_Tree_Monitoring {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    static int ans;//定义了一个静态变量 ans，用于记录覆盖整个二叉树所需的最小摄像头数量。静态变量的作用是在整个类的范围内共享这个数据，确保在不同方法调用之间能够正确地累加摄像头数量。
    public int minCameraCover2(TreeNode root) {//接受一个二叉树的根节点root作为参数，并返回覆盖整个二叉树所需的最小摄像头数量。
        ans = 0;//用于记录总共需要的摄像头数量。
        if(f(root) == 0) ans ++;//返回0，表示根节点需要一个摄像头（因为它的子节点和子树已经覆盖了它），则ans增加1。
        return ans;//最后返回 ans，即覆盖整个二叉树所需的最小摄像头数量。
    }
    public static int f(TreeNode x) {//用于遍历二叉树并确定在每个节点上放置摄像头的最佳方式。
        if(x == null) return 1;//如果当前节点x为空，返回1。这里的1表示空节点不需要摄像头，也不被任何摄像头覆盖，但是它的存在对于其父节点来说相当于一个“覆盖”状态。例如，一个节点的左子树为空，对于该节点来说，左子树方向相当于已经被 “覆盖” 了。
        int l = f(x.left);//对于非空节点，递归调用f方法处理左子树和右子树，分别获取左右子节点的返回值l和r。
        int r = f(x.right);//通过递归，从叶子节点开始向上处理每个节点。
        if(l == 0 || r == 0) {//如果l或r返回0，表示当前节点的一个子节点需要一个摄像头来覆盖，因此当前节点也需要一个摄像头，这是因为要覆盖子节点，必须在当前节点放置摄像头。ans增加1，返回2。这里的 2 表示当前节点放置了摄像头，并且该摄像头可以覆盖当前节点及其子节点。
            ans ++;
            return 2;
        }
        if(l == 1 && r == 1) return 0;//如果l和r都返回1，表示当前节点的两个子节点都不需要摄像头，当前节点也不需要，因为它已经被子节点的“覆盖”状态覆盖，返回0。这里的 0 表示当前节点不需要摄像头，但它没有被任何摄像头覆盖，需要其父节点来覆盖它。
        return 1;//如果其他情况，返回1，表示当前节点不需要摄像头，但是它的存在对于其父节点来说相当于一个“覆盖”状态。例如，一个子节点放置了摄像头，那么它的父节点就处于被覆盖的状态，虽然父节点本身不需要摄像头，但它对更上层的节点有 “覆盖” 的影响。
    }
}

假设我们有一个简单的二叉树：

    1
   / \
  2   3

首先调用 minCameraCover2(root)，ans 初始化为 0。
调用 f(root)：
- 对于节点 1，先递归调用 f(2) 和 f(3)。
- 对于节点 2，它没有子节点，f(2.left) 和 f(2.right) 都返回 1，因为子节点为空。由于左右子节点都返回 1，f(2) 返回 0，表示节点 2 需要被父节点覆盖。
- 对于节点 3，同理，f(3) 返回 0。
- 回到节点 1，因为 f(2) 和 f(3) 都返回 0，所以节点 1 需要一个摄像头，ans 增加 1，f(1) 返回 2。
由于 f(root) 返回 2，minCameraCover2 方法中不需要额外增加 ans，最后返回 ans，即 1，表示覆盖这个二叉树需要 1 个摄像头。