力扣Hot100系列17（Java）——[贪心算法] 总结 (买股票的最佳时机，跳跃游戏，跳跃游戏||，划分字母区间)
文章目录
- 前言
- 一、买股票的最佳时机
- 1.题目
- 2.代码
- 二、跳跃游戏
- 1.题目
- 2.代码
- 3.例子
- 三、跳跃游戏||
- 1.题目
- 2.代码
- 3.例子
- 四、划分字母区间
- 1.题目
- 2.代码
- 3.例子
前言
本文记录力扣Hot100里面关于贪心算法的四道题，包括常见解法和一些关键步骤理解，也有例子便于大家理解
一、买股票的最佳时机
1.题目
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
2.代码
public class Solution {
// 定义方法，接收价格数组，返回最大利润
public int maxProfit(int prices[]) {
// 1. 初始化最小价格为整数最大值（Integer.MAX_VALUE 是 Java 中 int 类型能表示的最大数，约 21 亿）
// 目的：确保数组中第一个价格一定能替换掉这个初始值
int minprice = Integer.MAX_VALUE;
// 2. 初始化最大利润为 0（如果所有情况都亏损，直接返回 0）
int maxprofit = 0;
// 3. 遍历价格数组的每一天
for (int i = 0; i < prices.length; i++) {
// 4. 更新当前遇到的最小价格
// 如果当天价格比记录的最小价格更低，就更新最小价格（相当于“找到更优的买入点”）
if (prices[i] < minprice) {
minprice = prices[i];
}
// 5. 计算当天卖出的利润，并更新最大利润
// 如果当天价格 - 最小价格 > 当前最大利润，说明当天卖出能赚更多，更新最大利润
else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
// 6. 返回最终的最大利润
return maxprofit;
}
}
这个大家肯定能理解，就不举例子了。
二、跳跃游戏
1.题目
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
2.代码
public class Solution {
public boolean canJump(int[] nums) {
// 1. 获取数组长度 n，最后一个位置的下标是 n-1
int n = nums.length;
// 2. 初始化「当前能到达的最远位置」为 0（初始只能站在下标 0 的位置）
int rightmost = 0;
// 3. 遍历数组的每个位置
for (int i = 0; i < n; ++i) {
// 4. 当前位置 i 是能到达的（在最远范围内）
if (i <= rightmost) {
// 5. 更新最远位置：取当前最远位置 和 「i位置能跳到的最远位置(i + nums[i])」的较大值
rightmost = Math.max(rightmost, i + nums[i]);
// 6. 提前终止：如果最远位置已经能覆盖最后一个下标，直接返回true
if (rightmost >= n - 1) {
return true;
}
}
// 7. 如果 i > rightmost，说明当前位置都到不了，后续位置更到不了，循环会继续但不会进入if，最终返回false
}
// 8. 遍历完都没覆盖最后一个下标，返回false
return false;
}
}
3.例子
例子1：能跳到终点（输入 nums = [2,3,1,1,4]）
数组长度 n = 5，最后一个下标是 4，我们逐行看代码执行过程：
| 循环次数 | i (当前位置) | i <= rightmost? | i + nums[i] | rightmost 更新后 | 是否 >= 4? | 执行结果 |
|---|---|---|---|---|---|---|
| 初始 | - | - | - | 0 | - | - |
| 第1次 | 0 | 0 <= 0 ✅ | 0+2=2 | max(0,2)=2 | 2 < 4 ❌ | 继续 |
| 第2次 | 1 | 1 <= 2 ✅ | 1+3=4 | max(2,4)=4 | 4 >= 4 ✅ | 直接返回 true |
- 初始：
rightmost = 0（只能站在起点下标0）。 - i=0（位置0）：
- 0 ≤ 0，满足条件；
- 位置0能跳2步，最远到下标2，所以
rightmost更新为2； - 2 < 4，不触发提前返回，继续循环。
- i=1（位置1）：
- 1 ≤ 2，满足条件；
- 位置1能跳3步，最远到下标4（1+3）；
rightmost更新为4，此时4 ≥ 4（最后一个下标），直接返回true。
例子2：跳不到终点（输入 nums = [3,2,1,0,4]）
数组长度 n = 5，最后一个下标是 4，执行过程：
| 循环次数 | i (当前位置) | i <= rightmost? | i + nums[i] | rightmost 更新后 | 是否 >= 4? | 执行结果 |
|---|---|---|---|---|---|---|
| 初始 | - | - | - | 0 | - | - |
| 第1次 | 0 | 0 <= 0 ✅ | 0+3=3 | max(0,3)=3 | 3 < 4 ❌ | 继续 |
| 第2次 | 1 | 1 <= 3 ✅ | 1+2=3 | max(3,3)=3 | 3 < 4 ❌ | 继续 |
| 第3次 | 2 | 2 <= 3 ✅ | 2+1=3 | max(3,3)=3 | 3 < 4 ❌ | 继续 |
| 第4次 | 3 | 3 <= 3 ✅ | 3+0=3 | max(3,3)=3 | 3 < 4 ❌ | 继续 |
| 第5次 | 4 | 4 <= 3 ❌ | - | 不更新 | - | 继续 |
| 循环结束 | - | - | - | - | - | 返回 false |
- 初始：
rightmost = 0。 - i=0（位置0）：
- 0 ≤ 0，满足条件；
- 位置0能跳3步，最远到下标3，
rightmost更新为3； - 3 < 4，继续循环。
- i=1（位置1）：
- 1 ≤ 3，满足条件；
- 位置1能跳2步，最远到下标3，
rightmost还是3； - 继续循环。
- i=2（位置2）：
- 2 ≤ 3，满足条件；
- 位置2能跳1步，最远到下标3，
rightmost不变； - 继续循环。
- i=3（位置3）：
- 3 ≤ 3，满足条件；
- 位置3能跳0步，最远到下标3，
rightmost仍为3； - 继续循环。
- i=4（位置4）：
- 4 > 3，不满足条件，无法更新
rightmost；
- 4 > 3，不满足条件，无法更新
- 循环结束，
rightmost始终没到4，返回false。
三、跳跃游戏||
1.题目
给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
- 0 <= j <= nums[i] 且
- i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
2.代码
class Solution {
public int jump(int[] nums) {
int length = nums.length; // 数组长度
int end = 0; // 当前跳跃能到达的最远边界
int maxPosition = 0; // 遍历过程中能到达的全局最远位置
int steps = 0; // 记录跳跃次数
// 遍历数组（注意：只遍历到倒数第二个元素，因为到最后一个元素就不用跳了）
for (int i = 0; i < length - 1; i++) {
// 不断更新「能到达的最远位置」：当前位置i + 该位置能跳的最大长度nums[i]
maxPosition = Math.max(maxPosition, i + nums[i]);
// 当遍历到当前跳跃的边界时，说明需要进行一次新的跳跃
if (i == end) {
end = maxPosition; // 更新下一次跳跃的边界为当前能到达的最远位置
steps++; // 跳跃次数+1
}
}
return steps;
}
}
3.例子
以数组 nums = [2,3,1,1,4] 为例，一步步看执行过程：
- 初始状态：length=5，end=0，maxPosition=0，steps=0。
- 第一次循环（i=0）：
- maxPosition = max(0, 0+2) = 2；
- 此时 i == end（0==0），所以 end=2，steps=1；
- 第二次循环（i=1）：
- maxPosition = max(2, 1+3) = 4；
- i=1 != end=2，不更新跳跃次数；
- 第三次循环（i=2）：
- maxPosition = max(4, 2+1) = 4；
- 此时 i == end（2==2），所以 end=4，steps=2；
- 循环结束（因为 i < 4，i=3时：
- maxPosition = max(4, 3+1) = 4；
- i=3 != end=4，不更新；
- 循环到i=4时不满足 i < 4，直接退出）；
- 返回 steps=2，即最少需要2次跳跃（0→1→4，或0→2→4）。
四、划分字母区间
1.题目
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = “eccbbbbdec”
输出：[10]
2.代码
class Solution {
public List<Integer> partitionLabels(String s) {
// 定义数组存储每个小写字母最后一次出现的下标（a-z对应0-25）
int[] last = new int[26];
int length = s.length();
// 遍历字符串，记录每个字符最后出现的位置
for (int i = 0; i < length; i++) {
last[s.charAt(i) - 'a'] = i;
}
// 存储划分后的每个子串长度
List<Integer> partition = new ArrayList<Integer>();
// start：当前划分区间的起始下标；end：当前划分区间的结束下标
int start = 0, end = 0;
// 遍历字符串，动态确定每个划分区间
for (int i = 0; i < length; i++) {
// 更新当前区间的结束下标，确保包含当前字符的所有出现位置
end = Math.max(end, last[s.charAt(i) - 'a']);
// 当遍历到当前区间的结束位置时，完成一次划分
if (i == end) {
// 计算当前区间长度并加入结果
partition.add(end - start + 1);
// 重置起始下标，准备下一个区间
start = end + 1;
}
}
return partition;
}
}
3.例子
以String s = "ababcbacdef"为例
（字符下标：0:a,1:b,2:a,3:b,4:c,5:b,6:a,7:c,8:d,9:e,10:f）
步骤1：预处理 - 记录每个字符最后出现的下标
遍历字符串，更新 last 数组（仅列出关键字符）：
- 字符a：依次出现在0、2、6，最终
last[0] = 6（a的最后下标是6） - 字符b：依次出现在1、3、5，最终
last[1] = 5（b的最后下标是5） - 字符c：依次出现在4、7，最终
last[2] = 7（c的最后下标是7） - 字符d：出现在8，
last[3] = 8 - 字符e：出现在9，
last[4] = 9 - 字符f：出现在10，
last[5] = 10
步骤2：遍历字符串，动态划分区间
初始化：start = 0，end = 0，结果列表 partition = []
- i=0（字符a）：
- 计算
end = max(0, last[0]=6)→ end=6 - i(0) ≠ end(6)，无其他操作
- 计算
- i=1（字符b）：
- 计算
end = max(6, last[1]=5)→ end=6 - i(1) ≠ end(6)，无其他操作
- 计算
- i=2（字符a）：
- 计算
end = max(6, last[0]=6)→ end=6 - i(2) ≠ end(6)，无其他操作
- 计算
- i=3（字符b）：
- 计算
end = max(6, last[1]=5)→ end=6 - i(3) ≠ end(6)，无其他操作
- 计算
- i=4（字符c）：
- 计算
end = max(6, last[2]=7)→ end=7 - i(4) ≠ end(7)，无其他操作
- 计算
- i=5（字符b）：
- 计算
end = max(7, last[1]=5)→ end=7 - i(5) ≠ end(7)，无其他操作
- 计算
- i=6（字符a）：
- 计算
end = max(7, last[0]=6)→ end=7 - i(6) ≠ end(7)，无其他操作
- 计算
- i=7（字符c）：
- 计算
end = max(7, last[2]=7)→ end=7 - i(7) == end(7)，执行划分：
- 区间长度 = 7 - 0 + 1 = 8，将8加入partition（此时partition=[8]）
- 重置start = 7 + 1 = 8
- 计算
- i=8（字符d）：
- 计算
end = max(7, last[3]=8)→ end=8 - i(8) == end(8)，执行划分：
- 区间长度 = 8 - 8 + 1 = 1，加入partition（此时partition=[8,1]）
- 重置start = 8 + 1 = 9
- 计算
- i=9（字符e）：
- 计算
end = max(8, last[4]=9)→ end=9 - i(9) == end(9)，执行划分：
- 区间长度 = 9 - 9 + 1 = 1，加入partition（此时partition=[8,1,1]）
- 重置start = 9 + 1 = 10
- 计算
- i=10（字符f）：
- 计算
end = max(9, last[5]=10)→ end=10 - i(10) == end(10)，执行划分：
- 区间长度 = 10 - 10 + 1 = 1，加入partition（最终partition=[8,1,1,1]）
- 重置start = 10 + 1 = 11
- 计算
最终结果
partition = [8,1,1,1]，即原字符串被划分为4个子串，长度分别是8、1、1、1。
如果本篇文章对您有帮助，可以点赞，收藏或评论哦！！！关注主包不迷路，让我们一起向前进步吧！！
