力扣Hot100系列17（Java）——[贪心算法] 总结 (买股票的最佳时机，跳跃游戏，跳跃游戏||，划分字母区间)

2026-02-02 20:27:38 栏目：最新资讯 5 阅读

文章目录

前言
一、买股票的最佳时机
- 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；
循环结束，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