力扣热题 100：贪心算法专题经典题解析

系列文章目录

力扣热题 100：哈希专题三道题详细解析(JAVA)
力扣热题 100：双指针专题四道题详细解析(JAVA)
力扣热题 100：滑动窗口专题两道题详细解析（JAVA）
力扣热题 100：子串专题三道题详细解析(JAVA)
力扣热题 100：普通数组专题五道题详细解析(JAVA)
力扣热题 100：矩阵专题四道题详细解析（JAVA）
力扣热题 100：链表专题经典题解析(前7道)
力扣热题 100：链表专题经典题解析（后7道）
力扣热题 100：二叉树专题经典题解析（前8道）
力扣热题 100：二叉树专题进阶题解析（后7道）
力扣热题 100：图论专题经典题解析
力扣热题 100：回溯专题经典题解析
力扣热题 100：二分查找专题经典题解析
力扣热题 100：栈专题经典题解析
力扣热题 100：堆专题经典题解析
力扣热题 100：贪心算法专题经典题解析
力扣热题 100：动态规划专题经典题解析
力扣热题 100：多维动态规划专题经典题解析
力扣热题 100：技巧专题经典题解析

在力扣（LeetCode）平台上，贪心算法相关的题目是算法面试和练习中的重要部分。今天，我们就来详细解析贪心算法专题中的几道经典题目，帮助大家更好地理解解题思路和技巧。

一、买卖股票的最佳时机（题目 121）

1. 题目描述

给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。你可以尽可能多地进行交易（多次买卖股票），但每次交易只能买卖一次股票。求最大利润。

2. 示例

示例 1：

输入：prices = [7, 1, 5, 3, 6, 4]

输出：5

解释：在第 2 天（价格为 1）买入，在第 3 天（价格为 5）卖出，利润为 4。然后在第 4 天（价格为 3）买入，在第 5 天（价格为 6）卖出，利润为 3。总利润为 4 + 3 = 7。

3. 解题思路

这道题主要考察贪心算法的应用。我们可以遍历数组，记录当前最低价格，并计算每天卖出的利润，累加所有正利润即可得到最大利润。

4. 代码实现（Java）

public class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > 0) {
                maxProfit += price - minPrice;
                minPrice = price; // 重新设置买入点
            }
        }
        return maxProfit;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

二、跳跃游戏（题目 55）

1. 题目描述

给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素表示在该位置可以跳跃的最大步数。判断你是否能够到达最后一个位置。

2. 示例

示例 1：

输入：nums = [2, 3, 1, 1, 4]

输出：true

示例 2：

输入：nums = [3, 2, 1, 0, 4]

输出：false

3. 解题思路

这道题主要考察贪心算法的应用。我们可以维护一个变量 maxReach，表示当前能到达的最远位置。遍历数组，如果当前位置超过了 maxReach，则无法到达终点。否则，更新 maxReach 为当前能到达的最远位置。

4. 代码实现（Java）

public class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

三、跳跃游戏 II（题目 45）

1. 题目描述

给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素表示在该位置可以跳跃的最大步数。求到达最后一个位置的最小跳跃次数。

2. 示例

示例 1：

输入：nums = [2, 3, 1, 1, 4]

输出：2

解释：先跳 1 步到第 2 个位置，再跳 3 步到终点。

3. 解题思路

这道题主要考察贪心算法的应用。我们可以维护三个变量：end 表示当前能到达的最远位置，farthest 表示下一步能到达的最远位置，jumps 表示跳跃次数。遍历数组，更新 farthest，当到达 end 时，增加跳跃次数，并更新 end 为 farthest。

4. 代码实现（Java）

public class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int jumps = 0;
        int end = 0;
        int farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == end) {
                jumps++;
                end = farthest;
                if (end >= nums.length - 1) {
                    break;
                }
            }
        }
        return jumps;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

四、划分字母区间（题目 763）

1. 题目描述

给定一个字符串 s，将字符串划分成若干个连续的区间，每个区间内的字符都是唯一的。返回这些区间的长度列表。

2. 示例

示例 1：

输入：s = "ababcbacadefegdehijhklij"

输出：[9, 7, 8]

解释：划分结果为 “ababcbaca”、“defegde”、“hijhklij”。

3. 解题思路

这道题主要考察贪心算法的应用。我们可以先统计每个字符最后出现的位置，然后遍历字符串，维护当前区间的最远结束位置。当到达当前区间的最远结束位置时，记录区间长度，并开始新的区间。

4. 代码实现（Java）

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> result = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                result.add(end - start + 1);
                start = i + 1;
            }
        }
        return result;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是字符串的长度。我们只需要遍历字符串两次。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间（不包括结果列表）。

以上就是力扣热题 100 中与贪心算法相关的经典题目的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。