算法思想 - 贪心算法

1. 贪心算法思想

1.1 什么是贪心算法

贪心算法（Greedy Algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望最终结果是全局最好或最优的算法。贪心算法的核心理念是局部最优选择，即每一步都选择当前看来最优的决策，而不考虑整体问题的全局最优解。

贪心算法的关键特征：

1. 贪心选择性质：即问题的最优解包含其子问题的最优解。换句话说，通过一系列局部最优选择，可以得到全局最优解。
2. 最优子结构：一个问题的最优解包含其子问题的最优解。这意味着，解决整个问题可以分解为解决子问题，并将子问题的最优解组合起来。

1.2 贪心算法的步骤

1. 选择：在每一步选择中，选择当前状态下最优的选项。
2. 可行性：所做的选择必须是可行的，即满足问题的约束条件。
3. 局部最优：每一步的选择都应该使得当前部分解达到局部最优。
4. 不可回退：一旦做出选择，就不再回退或修改之前的选择。

1.3 如何判断一个问题是否适用贪心算法

贪心算法适用于那些可以通过局部最优选择来得到全局最优解的问题。然而，并不是所有的问题都适用于贪心算法。判断一个问题是否适合使用贪心算法，通常需要分析：

1. 贪心选择性质：是否可以通过一系列局部最优的选择来构建全局最优解。
2. 最优子结构：问题的最优解是否包含其子问题的最优解。

如果一个问题同时满足这两个条件，那么贪心算法可能是一个有效的解决方案。

1.4 贪心算法的优缺点

优点：

• 简单易实现：贪心算法通常具有简单明了的逻辑，易于理解和实现。
• 高效：在适用的情况下，贪心算法通常比动态规划、回溯等算法更高效，时间复杂度更低。

缺点：

• 不总能得到最优解：对于某些问题，贪心算法可能只能得到次优解或局部最优解，而非全局最优解。
• 需要问题具备特定性质：只有在问题满足贪心选择性质和最优子结构时，贪心算法才能保证得到最优解。

1.5 贪心算法存在的问题

• 无法保证最优解：贪心算法在某些情况下无法保证得到问题的最优解。
• 依赖具体问题特性：需要深入理解问题的特性，才能正确应用贪心策略。
• 选择策略的设计：设计一个有效的贪心选择策略可能具有挑战性。

2. 典型例题解析

例题 1：买卖股票的最佳时机 II

2.1 题目描述

题目来自：LeetCode 122. 买卖股票的最佳时机 II (opens new window)

给你一个整数数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多只能持有一股股票。你也可以在同一天先购买，然后再出售。

返回你能获得的 最大利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：
在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：
在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：
在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

2.2 思路分析

本题允许进行多次交易，且在任何时候只能持有一股股票。因此，我们可以通过贪心算法来求解最大利润。贪心策略如下：

• 累积所有的上升趋势：只要第二天的价格高于第一天的价格，就进行买入和卖出，累积这部分利润。

这种策略的正确性基于以下观察：

• 任意多个连续的上升天数中，只要每天都进行买卖，最终的总利润等于最低价买入，最高价卖出的利润。
• 累积多个小的利润，等同于累积一次大的利润。

因此，通过在每个价格上涨的情况下进行买卖，我们可以获得最大利润。

2.3 代码实现

方法一：贪心策略

class Solution {
    /**
     * 使用贪心算法求解最大利润
     * @param prices 股票价格数组
     * @return 最大利润
     */
    public int maxProfit(int[] prices) {
        int ans = 0; // 初始化总利润为0
        int n = prices.length; // 获取价格数组的长度
        // 从第二天开始遍历
        for (int i = 1; i < n; ++i) {
            // 如果今天的价格高于昨天的价格，累积利润
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans; // 返回总利润
    }
}

代码说明：

1. 初始化变量：
   • ans：用于存储累计的总利润，初始值为0。
   • n：股票价格数组的长度。
2. 遍历价格数组：
   • 从第二天（索引1）开始，遍历到最后一天。
   • 对于每一天，比较当前价格 prices[i] 与前一天的价格 prices[i - 1]。
   • 如果当前价格高于前一天，则累积这部分利润 prices[i] - prices[i - 1]。
   • 使用 Math.max(0, prices[i] - prices[i - 1]) 确保只有在当前价格高于前一天时才累积利润，否则累积0。
3. 返回结果：
   • 遍历结束后，ans 包含了所有累积的利润，返回 ans。

方法二：局部最优选择

除了累积所有上升趋势，我们还可以通过局部最优选择来实现相同的效果。

class Solution {
    /**
     * 使用局部最优选择求解最大利润
     * @param prices 股票价格数组
     * @return 最大利润
     */
    public int maxProfit(int[] prices) {
        int profit = 0; // 初始化总利润为0
        for (int i = 1; i < prices.length; i++) {
            // 如果今天的价格高于昨天，进行买卖，累积利润
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit; // 返回总利润
    }
}

代码说明：

1. 初始化变量：
   • profit：用于存储累计的总利润，初始值为0。
2. 遍历价格数组：
   • 从第二天（索引1）开始，遍历到最后一天。
   • 对于每一天，检查当前价格是否高于前一天的价格。
   • 如果高于，则进行买入和卖出操作，累积这部分利润 prices[i] - prices[i - 1]。
3. 返回结果：
   • 遍历结束后，profit 包含了所有累积的利润，返回 profit。

方法三：更简洁的实现

class Solution {
    /**
     * 使用更简洁的贪心算法实现最大利润
     * @param prices 股票价格数组
     * @return 最大利润
     */
    public int maxProfit(int[] prices) {
        int totalProfit = 0; // 初始化总利润为0
        for (int i = 1; i < prices.length; i++) {
            // 累积所有上涨的差值
            if (prices[i] > prices[i - 1]) {
                totalProfit += prices[i] - prices[i - 1];
            }
        }
        return totalProfit; // 返回总利润
    }
}

代码说明：

该方法与方法二逻辑相同，只是变量名称更具可读性，便于理解。

---

例题 2：根据身高重建队列

2.4 题目描述

题目来自：LeetCode 406. 根据身高重建队列 (opens new window)

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 7，前面有 0 个身高大于或等于 7 的人。
编号为 1 的人身高为 4，前面有 4 个身高大于或等于 4 的人。
编号为 2 的人身高为 7，前面有 1 个身高大于或等于 7 的人。
编号为 3 的人身高为 5，前面有 0 个身高大于或等于 5 的人。
编号为 4 的人身高为 6，前面有 1 个身高大于或等于 6 的人。
编号为 5 的人身高为 5，前面有 2 个身高大于或等于 5 的人。
因此，[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

2.5 思路分析

本题需要根据身高和前面的人数来重建队列。贪心算法的核心在于先处理身高高的人，再处理身高低的人，以确保在插入时高个子的人已经排在前面，从而保证插入的位置准确。

具体步骤如下：

1. 排序：
   • 首先，对 people 数组进行排序，排序规则为：
     • 身高降序：身高高的人排在前面。
     • k值升序：身高相同的人，按照 k 值从小到大排序。
   • 这样排序的好处是：身高高的人会先被处理，而身高相同的人会按照 k 值的大小依次插入。
2. 插入：
   • 使用一个空的列表 ans 来表示最终的队列。
   • 遍历排序后的 people 数组，将每个人插入到 ans 中的第 k 个位置。
   • 由于我们已经按照身高降序排序，高个子的人先被插入，插入的位置不会影响到后面低个子人的插入。

为什么这样排序和插入能正确重建队列？

• 身高降序确保了当我们插入一个人时，已经插入的所有人都是身高大于或等于当前人的，这样插入的位置 k 就能准确反映当前人在队列中的位置。
• k值升序确保了同一身高的人按照前面较少的人数依次插入，不会影响到其他人的位置。

2.6 代码实现

方法一：按照身高降序，k值升序排序后插入

class Solution {
    /**
     * 根据身高重建队列的贪心算法实现
     * @param people 输入的二维数组，每个元素表示一个人的身高和前面的人数
     * @return 重建后的队列
     */
    public int[][] reconstructQueue(int[][] people) {
        // 对数组进行排序
        Arrays.sort(people, (person1, person2) -> {
            if (person1[0] != person2[0]) {
                // 身高降序排序
                return person2[0] - person1[0];
            } else {
                // k值升序排序
                return person1[1] - person2[1];
            }
        });

        // 使用列表来方便插入操作
        List<int[]> ans = new ArrayList<>();
        // 遍历排序后的数组，将每个人插入到对应的位置
        for (int[] person : people) {
            // person[1] 表示该人的前面应该有 person[1] 个身高大于或等于他的人
            ans.add(person[1], person);
        }

        // 将列表转换为二维数组返回
        return ans.toArray(new int[0][]);
    }
}

代码说明：

1. 排序：
   • 使用 Arrays.sort 方法对 people 数组进行排序。
   • 比较器逻辑：
     • 如果两个人的身高不同，按照身高降序排序，即身高高的人排在前面。
     • 如果两个人的身高相同，按照 k 值升序排序，即 k 值小的人排在前面。
2. 插入：
   • 创建一个空的 List<int[]> ans 来存储重建后的队列。
   • 遍历排序后的 people 数组，对于每个人 person：
     • person[1] 表示该人前面应该有 k 个身高大于或等于他的人。
     • 由于列表 ans 已经按照身高降序排列，直接将 person 插入到索引 person[1] 的位置即可。
3. 返回结果：
   • 使用 ans.toArray(new int[0][]) 将列表转换为二维数组，符合题目要求的返回格式。

方法二：按照身高升序，k值降序排序后插入

class Solution {
    /**
     * 根据身高重建队列的另一种贪心算法实现
     * @param people 输入的二维数组，每个元素表示一个人的身高和前面的人数
     * @return 重建后的队列
     */
    public int[][] reconstructQueue(int[][] people) {
        // 对数组进行排序
        Arrays.sort(people, (person1, person2) -> {
            if (person1[0] != person2[0]) {
                // 身高升序排序
                return person1[0] - person2[0];
            } else {
                // k值降序排序
                return person2[1] - person1[1];
            }
        });

        int n = people.length;
        int[][] ans = new int[n][];
        // 遍历排序后的数组，将每个人插入到对应的位置
        for (int[] person : people) {
            int spaces = person[1] + 1; // 需要找到第 k + 1 个空位
            for (int i = 0; i < n; ++i) {
                // 如果当前位置为空，则可能是插入的位置
                if (ans[i] == null) {
                    spaces--;
                    if (spaces == 0) {
                        ans[i] = person; // 插入该位置
                        break;
                    }
                }
            }
        }
        return ans; // 返回重建后的队列
    }
}

代码说明：

1. 排序：
   • 使用 Arrays.sort 方法对 people 数组进行排序。
   • 比较器逻辑：
     • 如果两个人的身高不同，按照身高升序排序，即身高低的人排在前面。
     • 如果两个人的身高相同，按照 k 值降序排序，即 k 值大的排在前面。
2. 插入：
   • 创建一个大小为 n 的二维数组 ans，用于存储重建后的队列。
   • 遍历排序后的 people 数组，对于每个人 person：
     • spaces = person[1] + 1：需要找到第 k + 1 个空位来插入该人。
     • 遍历 ans 数组，找到第 spaces 个空位的位置 i，并将 person 插入到该位置。
     • if (ans[i] == null)：检查当前位置是否为空。
     • spaces--：找到一个空位，减少剩余需要找到的空位数。
     • if (spaces == 0)：当找到第 k + 1 个空位时，插入该人并跳出循环。
3. 返回结果：
   • 遍历结束后，ans 数组即为重建后的队列，返回 ans。

方法二的特点：

• 时间复杂度较高：由于需要遍历整个 ans 数组来找到合适的位置，时间复杂度为 O(n^2)。
• 适用性：该方法在某些情况下可能更直观，但相比方法一，效率较低。

方法一与方法二的对比：

• 方法一：利用排序后直接插入列表，利用了列表动态插入的特性，效率更高，时间复杂度为 O(n^2)，但常数项较低。
• 方法二：需要手动遍历空位插入，代码相对复杂，且效率较低。

因此，方法一 是更推荐的解决方案。

2.7 更高效的实现方式

在方法一中，我们使用了 List<int[]> 来进行插入操作。由于列表的插入操作在 ArrayList 中的时间复杂度为 O(n)，总的时间复杂度为 O(n^2)。但在实际问题规模较小的情况下，这种实现已经足够高效。

然而，如果需要处理更大规模的数据，可以考虑使用 链表 来优化插入操作，使插入时间复杂度降低至 O(1)（不过总的时间复杂度仍为 O(n^2)）。

使用 LinkedList 优化插入操作：

class Solution {
    /**
     * 使用 LinkedList 优化插入操作的重建队列
     * @param people 输入的二维数组，每个元素表示一个人的身高和前面的人数
     * @return 重建后的队列
     */
    public int[][] reconstructQueue(int[][] 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 进行插入操作，插入时间复杂度为 O(1)
        List<int[]> queue = new LinkedList<>();
        for (int[] person : people) {
            // 按照 k值插入到指定位置
            queue.add(person[1], person);
        }

        // 将列表转换为二维数组返回
        return queue.toArray(new int[0][]);
    }
}

代码说明：

1. 排序：
   • 与方法一相同，按照身高降序，k值升序进行排序。
2. 插入：
   • 使用 LinkedList 来存储重建后的队列。
   • 对于每个人 person，直接将其插入到列表的第 person[1] 个位置。
   • 由于 LinkedList 的插入操作在指定位置的时间复杂度为 O(1)，总体上提高了插入效率。
3. 返回结果：
   • 将 LinkedList 转换为二维数组返回。

注意事项：

• 使用 LinkedList 可以优化插入操作的时间复杂度，但在大多数实际问题中，使用 ArrayList 也能达到较好的性能。
• 在选择使用何种数据结构时，需要根据具体问题的规模和性质进行权衡。