Leetcode+JAVA+贪心III

134.加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -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 == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
输入保证答案唯一。

解题思路

问题核心：
有 n 个加油站，gas[i] 表示第 i 个加油站可加的油量，cost[i] 表示从第 i 到第 i+1 个加油站的耗油量。
油箱容量无限，初始为空，需找到一个起始站，使得汽车能绕环路一周（回到起点，油量非负）。
如果存在解，答案唯一；否则返回 -1。
贪心策略：
净油量计算：
对于每个加油站，计算净油量 res[i] = gas[i] - cost[i]，表示在站 i 加完油并开往下一站后的油量变化。
如果总净油量 sum(res[i]) < 0，无法绕一周，返回 -1（因为总油量不足以覆盖总消耗）。
起始点选择：
使用 currSum 跟踪从某个起始点开始的累计净油量。
如果在某个点 i，currSum < 0，说明从当前起始点 start 到 i 的路径不可行，重置 start = i + 1，并清零 currSum。
继续遍历，直到检查所有站。
为什么贪心有效：
总油量检查：如果 sum(res[i]) >= 0，存在至少一个解（题目保证唯一）。
局部失败处理：如果从某个起点 start 到 i 的 currSum < 0，则 start 到 i 之间的任何点都不能作为起点（因为油量会更早变负）。
唯一解：题目保证如果解存在，则唯一。贪心算法通过排除不可行起点，找到唯一可行起点。
环形处理：
环形路径通过数组循环模拟（i+1 模 n），但你的代码通过单次遍历和总和检查隐式处理环形约束。
时间复杂度：
单遍遍历数组：O(n)，其中 n 是 gas.length。
空间复杂度：O(n)（用于 res 数组），可优化为 O(1)（直接用 gas[i] - cost[i]）。

代码

import java.util.*;class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {// 创建净油量数组，res[i] = gas[i] - cost[i]int[] res = new int[gas.length];// sum 记录总净油量，currSum 记录当前路径的净油量int sum = 0, currSum = 0;// start 记录潜在的起始加油站索引int start = 0;// 遍历所有加油站for (int i = 0; i < res.length; i++) {// 计算第 i 个加油站的净油量res[i] = gas[i] - cost[i];// 更新总净油量sum += res[i];// 更新当前路径净油量currSum += res[i];// 如果当前路径油量为负，当前起点不可行if (currSum < 0) {currSum = 0; // 重置当前路径油量start = i + 1; // 将起点移到下一个加油站}}// 如果总净油量 < 0，无法绕一周if (sum < 0) {return -1;}// 返回唯一可行起点（或 -1 如果 start 越界）return start;}
}

135.分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
提示：
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

解题思路

问题核心：
给定数组 ratings，ratings[i] 表示第 i 个孩子的评分。
分配规则：
每个孩子至少 1 颗糖果。
如果 ratings[i] > ratings[i-1]，第 i 个孩子比第 i-1 个孩子多拿糖果。
如果 ratings[i] > ratings[i+1]，第 i 个孩子比第 i+1 个孩子多拿糖果。
目标：最小化总糖果数。
贪心策略：
初始化：
为每个孩子分配 1 颗糖果（满足“至少 1 颗”）。
两次遍历：
从左到右：处理评分递增的情况。如果 ratings[i] > ratings[i-1]，则 candies[i] = candies[i-1] + 1，确保左边邻居规则。
从右到左：处理评分递减的情况。如果 ratings[i] > ratings[i+1]，则 candies[i] = max(candies[i], candies[i+1] + 1)，确保右边邻居规则，并保留左遍历结果的最大值。
求和：累加 candies 数组，得到最小糖果数。
为什么贪心有效：
左遍历确保评分递增时糖果数递增，满足左侧约束。
右遍历修正评分递减的情况，确保右侧约束，同时取最大值避免破坏左遍历结果。
两次遍历综合考虑所有相邻关系，保证满足所有条件且糖果数最小。
时间复杂度：
初始化和两次遍历：O(n)。
求和：O(n)。
总计：O(n)。
空间复杂度：
O(n)（candies 数组）。

代码

import java.util.*;class Solution {public int candy(int[] ratings) {// 获取数组长度int n = ratings.length;// 初始化糖果数组，每个孩子至少 1 颗糖果int[] candies = new int[n];Arrays.fill(candies, 1);// 从左到右遍历：处理评分递增情况for (int i = 1; i < n; i++) {// 如果当前孩子评分高于前一个，分配更多糖果if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}// 从右到左遍历：处理评分递减情况for (int i = n - 2; i >= 0; i--) {// 如果当前孩子评分高于后一个，确保糖果数大于后一个if (ratings[i] > ratings[i + 1]) {// 取当前糖果数和后一个糖果数+1的最大值，保留左遍历结果candies[i] = Math.max(candies[i], candies[i + 1] + 1);}}// 计算总糖果数int sum = 0;for (int candy : candies) {sum += candy;}return sum;}
}

860.柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示：
1 <= bills.length <= 105
bills[i] 不是 5 就是 10 或是 20

解题思路

问题核心：
每位顾客支付 5、10 或 20 美元，购买一杯 5 美元的柠檬水，需找回 bill - 5 美元。
初始没有零钱，只能用收到的钞票找零。
目标：判断是否能为所有顾客正确找零，返回 true 或 false。
贪心策略：
跟踪零钱：
只需跟踪 5 美元和 10 美元钞票的数量（five 和 ten），因为 20 美元钞票无法用于找零（题目中找零只涉及 5 美元和 10 美元）。
处理每种账单：
5 美元：直接收下，增加 five++，无需找零。
10 美元：需找回 5 美元（10 - 5），消耗 1 张 5 美元钞票（five--），增加 1 张 10 美元钞票（ten++）。如果 five == 0，无法找零，返回 false。
20 美元：需找回 15 美元（20 - 5），有两种找零方式：
优先用 1 张 10 美元 + 1 张 5 美元（ten--, five--），以保留更多 5 美元钞票（因为 5 美元更灵活）。
如果没有 10 美元钞票，尝试用 3 张 5 美元（five -= 3）。
如果两者都不可行，返回 false。
为什么贪心有效：
优先使用 10 美元 + 5 美元找零 20 美元，减少对 5 美元钞票的消耗，因为 5 美元钞票对后续找零（10 美元或 20 美元）更关键。
每次决策局部最优（保留最多 5 美元钞票），确保全局可行性。
如果某次无法找零，说明零钱不足，返回 false；否则，遍历完成返回 true。
时间复杂度：
单遍遍历 bills 数组：O(n)，其中 n 是 bills.length。
总计：O(n)。
空间复杂度：
O(1)，仅使用两个变量（five 和 ten）。

代码

class Solution {public boolean lemonadeChange(int[] bills) {// 初始化 5 美元和 10 美元钞票数量int five = 0, ten = 0;// 遍历每位顾客支付的账单for (int bill : bills) {if (bill == 5) {// 收到 5 美元，无需找零，增加 5 美元钞票数量five++;} else if (bill == 10) {// 收到 10 美元，需找回 5 美元if (five == 0) {// 没有 5 美元钞票，无法找零return false;}five--; // 消耗 1 张 5 美元钞票ten++;  // 增加 1 张 10 美元钞票} else { // bill == 20// 收到 20 美元，需找回 15 美元if (ten > 0 && five > 0) {// 优先用 1 张 10 美元 + 1 张 5 美元找零ten--;five--;} else if (five >= 3) {// 否则用 3 张 5 美元找零five -= 3;} else {// 无法找零return false;}}}// 所有顾客都成功找零return true;}
}

406.根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 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 <= 106
0 <= ki < people.length
题目数据确保队列可以被重建

解题思路

问题核心：
给定数组 people，people[i] = [hi, ki] 表示第 i 个人身高为 hi，前面有 ki 个身高大于或等于 hi 的人。
目标是构造队列 queue，使得 queue[j] = [hj, kj] 表示队列第 j 位的属性，且满足 ki 条件。
题目保证队列可被重建，解唯一。
贪心策略：
排序：
按身高 hi 降序排序，若身高相同，则按 ki 升序排序。
理由：身高高的人应先安排，因为他们的 ki 表示前面高或等高的人数，优先处理高个子可以简化后续插入（矮个子的 ki 不会受高个子影响）。
身高相同按 ki 升序，确保 ki 较小的人先插入（因为他们需要更靠前的位置）。
插入：
遍历排序后的 people，将每个 person = [hi, ki] 插入到结果队列的索引 ki 处。
插入时，ki 表示前面应有 ki 个高或等高的人。由于已按身高降序排序，之前插入的人身高大于或等于当前 hi，插入到 ki 位置正好满足条件。
使用动态列表（ArrayList）支持按索引插入，插入后队列自动调整。
转换为数组：
将动态列表转换为 int[][] 数组返回。
为什么贪心有效：
按身高降序排序确保高个子优先安排，矮个子插入时不会影响高个子的 ki（因为矮个子身高小于之前的人）。
按 ki 插入保证每个人的 ki 约束（前面正好有 ki 个高或等高的人）。
题目保证解存在，排序和插入策略确保唯一正确队列。
时间复杂度：
排序：O(n log n)，其中 n 是 people.length。
插入：ArrayList 的插入操作为 O(n)，总共 n 次插入，O(n²)。
总计：O(n²)（插入操作主导）。
空间复杂度：
O(n)（queue 列表，不计输出数组）。

代码

import java.util.*;class Solution {public int[][] reconstructQueue(int[][] people) {// 按身高降序排序，若身高相同则按 ki 升序排序Arrays.sort(people, (a, b) -> {if (a[0] != b[0]) return b[0] - a[0]; // 身高降序（高的先处理）return a[1] - b[1]; // 身高相同，ki 升序（小的 ki 先插入）});// 使用动态列表存储重建的队列List<int[]> queue = new ArrayList<>();// 遍历排序后的数组，按 ki 插入到正确位置for (int[] person : people) {queue.add(person[1], person); // 在索引 person[1]（ki）处插入 person}// 将列表转换为 int[][] 数组return queue.toArray(new int[people.length][]);}
}