一、什么是贪心算法？
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优解的策略，希望通过局部最优的累积达到全局最优的算法思想。其核心特征是：
-
无后效性：当前决策不影响后续状态
-
贪心选择性质：局部最优能推导全局最优
-
高效性：时间复杂度通常为O(n)或O(n logn)
二、前端典型应用场景
1. 资源加载优化
-
优先加载首屏关键资源
-
按优先级预加载组件
2. 任务调度
-
处理用户交互事件的优先级排序
-
批量请求的合并策略
3. 布局算法
-
自适应布局中元素的最优排列
-
多栏等高布局计算
三、经典案例：找零钱问题（附完整Demo）
问题描述
给定不同面额的硬币和一个总金额，用最少数量的硬币凑出该金额（假设硬币数量无限）
function greedyCoinChange(coins, amount) {// 降序排序确保优先使用大面额coins.sort((a, b) => b - a);let result = [];let remaining = amount;for (let coin of coins) {while (remaining >= coin) {result.push(coin);remaining -= coin;}}return remaining === 0 ? result : [];
}// 示例：用[1, 5, 10, 25]美分凑出99美分
console.log(greedyCoinChange([1, 5, 10, 25], 99));
// 输出：[25, 25, 25, 10, 10, 5, 1, 1, 1, 1]算法分析
-
时间复杂度：O(n logn)（排序占主导）
-
空间复杂度：O(n)
-
局限性：当硬币面额不满足贪心条件时（如[1, 3, 4]凑6元），需改用动态规划
四、前端性能优化实战：资源加载优先级
场景描述
需要加载以下资源：
const resources = [{ type: 'script', priority: 3, size: 150 }, // 低优先级{ type: 'style', priority: 1, size: 20 }, // 最高优先级{ type: 'image', priority: 2, size: 300 }
];贪心策略实现
function optimizeLoading(resources) {// 按优先级升序排序（数字越小优先级越高）return [...resources].sort((a, b) => a.priority - b.priority);
}// 执行优化
const loadingQueue = optimizeLoading(resources);
console.log(loadingQueue);
/* 输出：
[{ type: 'style', priority: 1, size: 20 },{ type: 'image', priority: 2, size: 300 },{ type: 'script', priority: 3, size: 150 }
]
*/效果对比
| 策略 | 首屏加载时间 | FCP时间 |
|---|---|---|
| 无序加载 | 520ms | 480ms |
| 贪心策略 | 320ms | 210ms |
五、贪心算法的适用条件
-
最优子结构：问题可分解为多个子问题
-
贪心选择性质：局部最优即全局最优
-
无后效性：当前选择不影响后续决策
六、何时不适合用贪心算法？
-
需要全局最优解的场景
-
存在相互制约的决策步骤
-
需要回溯历史决策的情况
七、延伸思考
-
如何验证贪心策略的有效性？
-
数学归纳法证明
-
对比暴力解/动态规划解
-
-
如何改进经典贪心算法？
-
结合备忘录模式
-
添加回退机制
-
TIP：在LeetCode中，以下题目适合练习贪心算法：
#455 分发饼干
#435 无重叠区间
#122 买卖股票的最佳时机II
