134. 加油站
思路：每次遍历时，如果当前的油量差（currTank）小于0，说明从当前起点无法到达下一个加油站。此时，将下一个加油站设为新的起点，并重置当前油量差（currTank）。最后检查总的油量差（totalTank），如果总的油量差大于等于0，说明存在一个合法的起点，使汽车能绕完整个环形路；否则不存在。
题解：
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalTank = 0; // 记录总的油量差，用于判断当前起点是否能够到达下一个加油站。
int currTank = 0; // 记录当前的油量差，用于判断是否能够完成一整周的环绕。
int startStation = 0; // 记录起点加油站的索引
// 遍历每一个加油站
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i]; // 计算油量差
totalTank += diff; // 更新总油量差
currTank += diff; // 更新当前油量差
// 如果当前油量差小于0，说明从当前起点无法到达下一个加油站
if (currTank < 0) {
// 将下一个加油站设为新的起点
startStation = i + 1;
// 重置当前油量差
currTank = 0;
}
}
// 检查总的油量差是否大于等于0
return totalTank >= 0 ? startStation : -1; // 如果是，则返回起点索引，否则返回-1
}
135. 分发糖果
思路：分从左往右和从右往左两次遍历数组，确保每个孩子得到的糖果数满足局部最优的条件，即比左边或右边评分更高的孩子多分配糖果。
题解：
public int candy(int[] ratings) {
// 初始化一个数组用来存放每个孩子分配的糖果数，初始值都设为1
int[] counter = new int[ratings.length];
Arrays.fill(counter, 1);
// 从左向右遍历一遍，确保右边评分高的孩子糖果数比左边的多
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
counter[i] = counter[i - 1] + 1;
}
}
// 从右向左遍历一遍，确保左边评分高的孩子糖果数比右边的多
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
counter[i] = Math.max(counter[i], counter[i + 1] + 1);
}
}
// 计算总共分配的糖果数
int sum = 0;
for (int num : counter) {
sum += num;
}
return sum;
}
860.柠檬水找零
思路：贪心策略：优先使用较大面额的钞票进行找零，以确保有足够的小面额钞票应对后续可能的找零需求。
题解：
public boolean lemonadeChange(int[] bills) {
// 记录收到的10美元和5美元的钞票数量
int tenCount = 0;
int fiveCount = 0;
// 遍历每一个顾客给的钞票
for (int bill : bills) {
// 如果顾客给5美元，直接收下
if (bill == 5) {
fiveCount++;
}
// 如果顾客给10美元，需要找回5美元
else if (bill == 10) {
tenCount++;
fiveCount--;
}
// 如果顾客给20美元，需要找回15美元
else {
// 优先用一个10美元和一个5美元找零
if (tenCount > 0) {
tenCount--;
fiveCount--;
}
// 如果没有10美元，用三个5美元找零
else {
fiveCount -= 3;
}
}
// 如果五美元的钞票数量小于0，说明无法找零，返回false
if (fiveCount < 0) {
return false;
}
}
// 如果所有顾客都成功找零，返回true
return true;
}
406.根据身高重建队列
题目链接：406.根据身高重建队列
文档讲解：代码随想录
状态：不会
思路：遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。 因为h表示身高，k表示前面有几个人身高大于等于自己，所以先考虑按照身高降序，如果身高相同，按照k升序排序。然后左右到右遍历时，根据k插入到对应索引位置即可。
题解：
public int[][] reconstructQueue(int[][] people) {
// 首先按照规则对people数组进行排序
// 身高从高到低排序，如果身高相同，则按k值从小到大排序
Arrays.sort(people, (a, b) -> {
if (a[0] != b[0]) {
return b[0] - a[0]; // 身高降序排序
} else {
return a[1] - b[1]; // k值升序排序
}
});
// 创建一个链表用于插入排序后的结果
LinkedList<int[]> list = new LinkedList<>();
// 遍历排序后的数组，根据每个人的k值插入到链表的对应位置
for (int[] person : people) {
list.add(person[1], person); // 按照k值插入到链表中
}
// 将链表转换为二维数组，并返回
return list.toArray(new int[people.length][]);
}