LeetCode Day 贪心算法 第 2 部分

贪心算法是一种常见的算法设计策略，它通过每一步选择当前状态下最优的选择，从而希望在全局中得到最优解。近年来，面对复杂的算法题目，特别是在LeetCode这样的编程平台上，理解和掌握贪心算法变得越来越重要。在这篇文章中，我们将探讨LeetCode中贪心算法的第二部分，分析一些经典题目和解决思路。

贪心算法的基本原理

贪心算法的基本思想是“局部最优解推出全局最优解”。它通过一次选择最优的解决方案，希望在整体上也能获得最优结果。通常情况下，贪心算法适用于满足贪心选择性质和最优子结构性质的问题。

贪心算法的特点

贪心算法有几个显著的特点，理解这些特点对于解决相关问题至关重要：

不一定得到全局最优解

虽然贪心算法旨在通过局部选择最优解来引导达到全局优化，但并不是所有问题都可以通过这样的方式得到全局最优解。因此，在使用贪心算法时，需要对问题的性质有深入的理解。

适用性

对于某些特定类型的问题，贪心算法可以高效找到最优解。例如，最小生成树、单源最短路径等问题通常可以通过贪心策略解决。

LeetCode 经典贪心问题

在LeetCode中，有许多经典的贪心算法题目，下面我们将分析几个典型例子。

最大吞噬糖果数量

题目描述：在一个甜品店中，如果顾客选择了多种不同口味的糖果，每种糖果可以被选择一次并得到一定的数量。求如何选择糖果能够最大化总数量。

解法思路：我们可以首先对糖果数量进行排序，随后按降序遍历糖果，只需选择前k种糖果即可得到结果。

public int maximumCandies(int[] candies, int k) {
    Arrays.sort(candies);
    int result = 0;
    for (int i = candies.length - 1; i >= 0 && k > 0; i--) {
        result += Math.min(candies[i], k);
        k--;
    }
    return result;
}

以上代码首先对糖果数量进行了排序，然后逆序取前k个元素进行求和，从而得到最大糖果数量。

活动选择问题

题目描述：给定一系列活动，每个活动都有开始时间和结束时间，问如何选择活动才能使参与的活动数量最大。

解法思路：可以通过对活动结束时间进行排序，依次选择不冲突的活动，从而达到最大活动数量。

public int scheduleMaxActivities(int[][] activities) {
    Arrays.sort(activities, Comparator.comparingInt(a -> a[1]));
    int count = 0, lastEndTime = -1;
    for (int[] activity : activities) {
        if (activity[0] >= lastEndTime) {
            count++;
            lastEndTime = activity[1];
        }
    }
    return count;
}

此代码通过排序策略选择结束时间最早的活动，以此避免时间冲突并最大化可参与活动的数量。

结束语

通过本篇文章，我们对LeetCode的贪心算法相关问题进行了深入探讨。从贪心算法的基本原理到经典示例的应用，掌握这些知识对于打磨算法思维和提高解题能力都具有重要意义。希望未来能在更多的编程挑战中应用贪心算法，迎接新的算法挑战！