贪心算法

相关源文件

• README.md

目的与范围

本文档全面概述了 leetcode-master 仓库中实现的贪心算法。它涵盖了贪心算法的理论基础、常见问题模式以及使用贪心方法的特定 LeetCode 问题。关于有时会与贪心算法混淆的动态规划等相关算法策略，请参阅动态规划。

贪心算法简介

贪心算法是一种问题解决方法，它在每一步都做出局部最优选择，以期找到全局最优解。在算法的每个阶段，都会选择当前最有利的选择，而不考虑整个问题状态。

来源： README.md257

主要特点

• 贪心选择性质：通过做出局部最优选择可以达到全局最优解。
• 最优子结构：最优解包含其子问题的最优解。
• 无回溯：一旦做出选择，就不会重新考虑。
• 易于实现：通常比动态规划更容易实现。
• 效率：通常能产生高效的算法。

何时使用贪心算法

贪心算法适用于

1. 问题具有最优子结构
2. 问题具有贪心选择性质
3. 局部最优导致全局最优

贪心算法并非总能为每个问题提供最优解，但它们通常能提供很好的近似解，并且在效率是首要考虑因素时非常有用。

贪心算法问题类型

leetcode-master 仓库将贪心算法问题分为几类

来源： README.md258-280

问题列表

该仓库涵盖了以下贪心算法问题

问题	LeetCode ID	类别	关键思路
分配饼干	455	基础	将较小的饼干分配给不太贪婪的孩子
摆动序列	376	序列	计算序列中的峰值和谷值
最大子数组	53	序列	当总和变为负数时重置总和
买卖股票的最佳时机 II	122	序列	捕捉每一次价格上涨
跳跃游戏	55	序列	跟踪最大可达位置
跳跃游戏 II	45	序列	基于最大范围优化跳跃
K 次取反最大化总和	1005	基础	首先取反最小的值
加油站	134	其他	找到具有足够油量的起始位置
糖果	135	基础	满足双向约束
柠檬水找零	860	基础	找零时最大化使用大面额纸币
按高度重构队列	406	其他	根据身高和位置进行插入
用最少箭数引爆气球	452	间隔	优化重叠区间
非重叠区间	435	间隔	移除最少的区间以避免重叠
分割标签	763	间隔	跟踪每个字符的最后出现位置
合并区间	56	间隔	排序并合并重叠区间
单调递增数字	738	其他	修改数字以确保单调性
二叉树摄像头	968	其他	战略性摄像头放置

来源： README.md258-279

贪心算法实现过程

实现贪心算法的过程通常遵循以下步骤

来源： README.md257-280

区间问题：贪心算法的关键应用

区间问题是贪心算法最重要的应用之一。这些问题通常涉及一组区间（带有开始和结束点），需要决定如何最优地选择、合并或处理这些区间。

常见的区间问题模式

1. 区间选择：选择不重叠区间数的最大值
2. 区间合并：合并重叠区间
3. 区间覆盖：覆盖所有区间所需的最小点/区间

来源： README.md272-276

基于序列的问题

序列问题构成了贪心算法的另一大类，处理数组或序列，其中局部最优选择导向全局最优。

股票问题

该仓库涵盖了股票交易问题，目标是通过买卖股票来最大化利润。

来源： README.md262

跳跃游戏

跳跃游戏是另一个有趣的序列问题，它运用了贪心策略。

来源： README.md263-264

高级应用

该仓库还涵盖了一些不属于上述类别的高级贪心算法应用

1. 二叉树摄像头：一个结合了树遍历和贪心优化以高效放置摄像头的题目。
2. 队列重建：根据人们的身高和位置重建队列。
3. 单调递增数字：找到具有单调递增数字的最大数字。

与其他算法的关系

贪心算法在算法学习路径中占有重要地位，它建立在基础数据结构和算法之上，同时为动态规划等更复杂的方法奠定基础。

来源： README.md154-166

总结

贪心算法在局部最优选择导向全局最优时，为各种问题提供了高效的解决方案。leetcode-master 仓库通过精心挑选的问题，展示了各种贪心技术和模式，提供了一种系统性的学习和应用贪心算法的方法。

理解这些问题和模式，可以为应对更复杂的算法挑战打下坚实的基础，并能洞察何时应该使用贪心方法，何时需要使用动态规划等更复杂的技术。

来源： README.md250-280