贪心

0 Basic 贪心是什么？ 每一步都做当前看起来最优的选择，期望最终得到全局最优解 与动态规划的区别： DP：考虑所有子问题的组合，自底向上构建全局最优 贪心：只看当前一步，不回头，不考虑未来 贪心：每个岔路口走看起来最近的路 DP ：先算出所有路的长度，再选最优 贪心快（O(n)），但不是所有问题都适用 DP 慢（O(n²) 或更高），但一定正确 贪心常见策略： 策略 描述 典型题 排序贪心 先排序再按顺序决策 合并区间、划分字母区间 维护极值 遍历中维护当前最优 买卖股票、跳跃游戏 区间贪心 按端点排序选最优区间 无重叠区间、合并区间 反悔贪心 先贪心选，发现更优时替换 较少见，进阶题 1 买卖股票的最佳时机 | Easy 题目：prices[i] 是第 i 天的价格。只能买一次卖一次(先买后卖),求最大利润;不交易返回0 [7,1,5,3,6,4] → 5（第 2 天买，第 5 天卖，6-1=5） 思路分析： 贪心直觉：我想在之前的最低点买入，在今天卖出 遍历价格，维护到目前为止的最低买入价。对于每一天，计算"今天卖出的利润"并更新最大值 踩坑记录： 想好初始值设置，一般最低就设置为float("inf")，最高设置为float("-inf") 代码： 1class Solution: 2 def maxProfit(self, prices: List[int]) -> int: 3 min_price = float("inf") 4 best = 0 5 6 for p in prices: 7 best = max(best, p - min_price) 8 min_price = min(p, min_price) 9 10 return best 复杂度： ...