贪心算法（Greedy Algorithms）完全详解 - 从零精通¶

def greedy_algorithm():
    """
    贪心算法通用框架
    """
    # 第1步：预处理（通常是排序）
    # 排序是贪心算法最常见的第一步！
    items.sort(key=lambda x: x.some_attribute)

    result = []

    # 第2步：贪心选择
    for item in items:
        if is_compatible(item, result):  # 判断是否兼容
            result.append(item)  # 贪心选择

    return result

# 示例：活动选择问题
def activity_selection(activities):
    """
    activities: [(开始时间, 结束时间), ...]
    """
    # 第1步：按结束时间排序
    activities.sort(key=lambda x: x[1])

    result = []
    last_end = -float('inf')

    # 第2步：贪心选择最早结束的
    for start, end in activities:
        if start >= last_end:  # 不冲突
            result.append((start, end))
            last_end = end

    return result

def activity_selection(activities):
    """
    活动选择问题（贪心）
    时间：O(n log n)
    空间：O(1)

    activities: [(开始时间, 结束时间), ...]
    """
    if not activities:
        return []

    # 第1步：按结束时间排序（贪心策略）
    activities.sort(key=lambda x: x[1])

    print("活动（按结束时间排序）:")
    for i, (start, end) in enumerate(activities):
        print(f"  活动{i}: [{start}, {end}]")

    # 第2步：贪心选择
    result = []
    last_end = -float('inf')

    print("\n贪心选择过程:")
    for i, (start, end) in enumerate(activities):
        if start >= last_end:
            result.append((start, end))
            last_end = end
            print(f"  ✓ 选择活动{i}: [{start}, {end}]")
        else:
            print(f"  ✗ 跳过活动{i}: [{start}, {end}] (与上次选择的活动冲突)")

    print(f"\n最多能参加 {len(result)} 个活动")
    return result

# 测试
print("=" * 60)
print("活动选择问题")
print("=" * 60)

activities = [
    (0, 6),   # 活动1
    (3, 4),   # 活动2
    (1, 2),   # 活动3
    (5, 7),   # 活动4
    (8, 9),   # 活动5
    (5, 9),   # 活动6
]

result = activity_selection(activities)

# 输出：
# ============================================================
# 活动选择问题
# ============================================================
# 活动（按结束时间排序）:
#   活动0: [1, 2]    ← 最早结束
#   活动1: [3, 4]
#   活动2: [0, 6]
#   活动3: [5, 7]
#   活动4: [8, 9]
#   活动5: [5, 9]
#
# 贪心选择过程:
#   ✓ 选择活动0: [1, 2]    ← 选最早结束的
#   ✓ 选择活动1: [3, 4]
#   ✗ 跳过活动2: [0, 6] (与上次选择的活动冲突)
#   ✗ 跳过活动3: [5, 7] (与上次选择的活动冲突)
#   ✓ 选择活动4: [8, 9]
#   ✗ 跳过活动5: [5, 9] (与上次选择的活动冲突)
#
# 最多能参加 3 个活动
#
# 结果：[1,2], [3,4], [8,9]

def erase_overlap_intervals(intervals):
    """
    无重叠区间（贪心）
    时间：O(n log n)
    空间：O(1)
    """
    if not intervals:
        return 0

    # 第1步：按结束时间排序
    intervals.sort(key=lambda x: x[1])

    print("区间（按结束时间排序）:")
    for i, interval in enumerate(intervals):
        print(f"  {i}: {interval}")

    # 第2步：贪心选择不重叠的区间
    count = 1  # 选中第一个区间
    last_end = intervals[0][1]

    print("\n贪心选择:")
    print(f"  选择区间0: {intervals[0]}")

    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start >= last_end:  # 不重叠
            count += 1
            last_end = end
            print(f"  选择区间{i}: {intervals[i]}")
        else:
            print(f"  跳过区间{i}: {intervals[i]} (重叠)")

    # 需要移除的数量
    remove = len(intervals) - count
    print(f"\n最大不重叠区间数: {count}")
    print(f"需要移除: {remove}")
    return remove

# 测试
print("\n" + "=" * 60)
print("无重叠区间")
print("=" * 60)

intervals = [[1,2], [2,3], [3,4], [1,3]]
result = erase_overlap_intervals(intervals)

# 输出：
# ============================================================
# 无重叠区间
# ============================================================
# 区间（按结束时间排序）:
#   0: [1, 2]
#   1: [1, 3]
#   2: [2, 3]
#   3: [3, 4]
#
# 贪心选择:
#   选择区间0: [1, 2]
#   跳过区间1: [1, 3] (重叠)
#   选择区间2: [2, 3]
#   选择区间3: [3, 4]
#
# 最大不重叠区间数: 3
# 需要移除: 1

def find_min_arrow_shots(points):
    """
    用最少数量的箭射爆气球
    时间：O(n log n)

    points: [[x_start, x_end], ...]
    """
    if not points:
        return 0

    # 按结束位置排序
    points.sort(key=lambda x: x[1])

    arrows = 1
    last_end = points[0][1]

    for start, end in points[1:]:  # 切片操作：[start:end:step]提取子序列
        if start > last_end:  # 不重叠，需要新箭
            arrows += 1
            last_end = end
        # 否则重叠，一箭可以射爆多个

    return arrows

def can_jump(nums):
    """
    跳跃游戏（贪心）
    时间：O(n)
    空间：O(1)
    """
    if not nums:
        return False

    max_reach = 0  # 当前能到达的最远位置

    print("跳跃过程:")
    for i, jump in enumerate(nums):  # enumerate同时获取索引和值
        print(f"\n位置{i}: 可跳{jump}步")
        print(f"  当前最远: {max_reach}")

        if i > max_reach:
            print(f"  ✗ 到不了位置{i}")
            return False

        # 更新最远位置
        new_reach = i + jump
        if new_reach > max_reach:
            max_reach = new_reach
            print(f"  更新最远位置: {max_reach}")

        if max_reach >= len(nums) - 1:
            print(f"  ✓ 能到达末尾！")
            return True

    return max_reach >= len(nums) - 1

# 测试
print("\n" + "=" * 60)
print("跳跃游戏")
print("=" * 60)

nums1 = [2, 3, 1, 1, 4]
print(f"\n示例1: {nums1}")
result1 = can_jump(nums1)

nums2 = [3, 2, 1, 0, 4]
print(f"\n示例2: {nums2}")
result2 = can_jump(nums2)

# 输出：
# ============================================================
# 跳跃游戏
# ============================================================
#
# 示例1: [2, 3, 1, 1, 4]
# 跳跃过程:
#
# 位置0: 可跳2步
#   当前最远: 0
#   更新最远位置: 2
#
# 位置1: 可跳3步
#   当前最远: 2
#   更新最远位置: 4
#   ✓ 能到达末尾！
#
# 示例2: [3, 2, 1, 0, 4]
# 跳跃过程:
#
# 位置0: 可跳3步
#   当前最远: 0
#   更新最远位置: 3
#
# 位置1: 可跳2步
#   当前最远: 3
#
# 位置2: 可跳1步
#   当前最远: 3
#
# 位置3: 可跳0步
#   当前最远: 3
#
# 位置4: 可跳4步
#   当前最远: 3
#   ✗ 到不了位置4

def jump_ii(nums):
    """
    跳跃游戏II（贪心：BFS层序遍历思想）
    时间：O(n)
    空间：O(1)
    """
    if len(nums) <= 1:
        return 0

    jumps = 0
    current_end = 0  # 当前跳跃能到的边界
    farthest = 0     # 当前层能到的最远位置

    print("跳跃过程（BFS层序）:")

    for i in range(len(nums) - 1):  # 不需要访问最后一个位置
        # 更新当前层能到的最远位置
        farthest = max(farthest, i + nums[i])

        print(f"位置{i}: 可跳{nums[i]}步, 当前层最远: {farthest}")

        # 到达当前跳跃的边界
        if i == current_end:
            jumps += 1
            current_end = farthest
            print(f"  跳跃{jumps}: 当前边界更新为{current_end}")

            if current_end >= len(nums) - 1:
                break

    print(f"\n最小跳跃次数: {jumps}")
    return jumps

# 测试
print("\n" + "=" * 60)
print("跳跃游戏II - 最小跳跃次数")
print("=" * 60)

nums = [2, 3, 1, 1, 4]
print(f"输入: {nums}")
result = jump_ii(nums)

# 输出：
# ============================================================
# 跳跃游戏II - 最小跳跃次数
# ============================================================
# 输入: [2, 3, 1, 1, 4]
# 跳跃过程（BFS层序）:
# 位置0: 可跳2步, 当前层最远: 2
#   跳跃1: 当前边界更新为2
# 位置1: 可跳3步, 当前层最远: 4
# 位置2: 可跳1步, 当前层最远: 4
#   跳跃2: 当前边界更新为4
#
# 最小跳跃次数: 2

import heapq
from collections import defaultdict  # defaultdict带默认值的字典，避免KeyError

class HuffmanNode:
    """霍夫曼树节点"""
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char      # 字符（叶子节点）
        self.freq = freq      # 频率
        self.left = left      # 左子节点
        self.right = right    # 右子节点

    def __lt__(self, other):
        # 用于堆排序（按频率比较）
        return self.freq < other.freq

def huffman_encoding(chars, freqs):
    """
    霍夫曼编码（贪心）
    时间：O(n log n)
    空间：O(n)
    """
    # 第1步：创建节点并放入最小堆
    heap = []
    for char, freq in zip(chars, freqs):  # zip并行遍历多个可迭代对象
        node = HuffmanNode(char=char, freq=freq)
        heapq.heappush(heap, node)
        print(f"创建节点: {char}({freq})")

    # 第2步：贪心合并（每次取频率最小的两个）
    print("\n构建霍夫曼树:")
    step = 1

    while len(heap) > 1:
        # 取出频率最小的两个节点
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)

        # 合并
        merged_freq = left.freq + right.freq
        merged_node = HuffmanNode(freq=merged_freq, left=left, right=right)

        print(f"\n步骤{step}:")
        print(f"  取出: {left.char if left.char else 'Node'}({left.freq}) 和 "
              f"{right.char if right.char else 'Node'}({right.freq})")
        print(f"  合并: 频率 = {merged_freq}")

        heapq.heappush(heap, merged_node)
        step += 1

    # 第3步：生成编码
    root = heap[0]
    codes = {}

    def generate_codes(node, code=""):
        if node is None:
            return

        # 叶子节点
        if node.char is not None:
            codes[node.char] = code if code else "0"
            return

        # 左边加0，右边加1
        generate_codes(node.left, code + "0")
        generate_codes(node.right, code + "1")

    generate_codes(root)

    print("\n霍夫曼编码:")
    total_length = 0
    for char, code in sorted(codes.items()):
        freq = freqs[chars.index(char)]
        length = freq * len(code)
        total_length += length
        print(f"  {char}: {code} (长度={len(code)}, 贡献={length})")

    print(f"\n总编码长度: {total_length}")
    return codes

# 测试
print("\n" + "=" * 60)
print("霍夫曼编码")
print("=" * 60)

chars = ['A', 'B', 'C', 'D', 'E']
freqs = [5, 9, 12, 13, 16]

print(f"字符频率: {dict(zip(chars, freqs))}")
codes = huffman_encoding(chars, freqs)

# 输出：
# ============================================================
# 霍夫曼编码
# ============================================================
# 字符频率: {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16}
# 创建节点: A(5)
# 创建节点: B(9)
# 创建节点: C(12)
# 创建节点: D(13)
# 创建节点: E(16)
#
# 构建霍夫曼树:
#
# 步骤1:
#   取出: A(5) 和 B(9)
#   合并: 频率 = 14
#
# 步骤2:
#   取出: C(12) 和 D(13)
#   合并: 频率 = 25
#
# 步骤3:
#   取出: Node(14) 和 E(16)
#   合并: 频率 = 30
#
# 步骤4:
#   取出: Node(25) 和 Node(30)
#   合并: 频率 = 55
#
# 霍夫曼编码:
#   A: 100 (长度=3, 贡献=15)
#   B: 101 (长度=3, 贡献=27)
#   C: 00 (长度=2, 贡献=24)
#   D: 01 (长度=2, 贡献=26)
#   E: 11 (长度=2, 贡献=32)
#
# 总编码长度: 124

def fractional_knapsack(weights, values, capacity):
    """
    分数背包问题（贪心）
    时间：O(n log n)
    空间：O(1)
    """
    n = len(weights)

    # 第1步：计算单位价值并排序
    items = []
    for i in range(n):
        unit_value = values[i] / weights[i]
        items.append((weights[i], values[i], unit_value, i))

    # 按单位价值降序排序
    items.sort(key=lambda x: x[2], reverse=True)  # lambda匿名函数：简洁的单行函数

    print("物品（按单位价值排序）:")
    print("  物品  重量  价值  单位价值")
    for w, v, uv, idx in items:
        print(f"  {chr(65+idx)}    {w:2d}   {v:3d}   {uv:.2f}")

    # 第2步：贪心选择
    total_value = 0
    remaining = capacity
    result = []

    print("\n贪心选择过程:")

    for w, v, uv, idx in items:
        if remaining >= w:
            # 全部拿
            total_value += v
            remaining -= w
            result.append((chr(65+idx), 1.0))
            print(f"  全拿{chr(65+idx)}: 重量={w}, 价值={v}, 剩余容量={remaining}")
        else:
            # 拿一部分
            fraction = remaining / w
            take_value = v * fraction
            total_value += take_value
            result.append((chr(65+idx), fraction))
            print(f"  拿{chr(65+idx)}的{fraction:.2%}: 重量={remaining}, 价值={take_value:.2f}")
            break

    print(f"\n总价值: {total_value:.2f}")
    return total_value, result

# 测试
print("\n" + "=" * 60)
print("分数背包问题")
print("=" * 60)

weights = [10, 20, 30]
values = [60, 100, 160]
capacity = 50

print(f"背包容量: {capacity}")
total_value, result = fractional_knapsack(weights, values, capacity)

# 输出：
# ============================================================
# 分数背包问题
# ============================================================
# 背包容量: 50
# 物品（按单位价值排序）:
#   物品  重量  价值  单位价值
#   A    10   60   6.00
#   C    30   160  5.33
#   B    20   100  5.00
#
# 贪心选择过程:
#   全拿A: 重量=10, 价值=60, 剩余容量=40
#   全拿C: 重量=30, 价值=160, 剩余容量=10
#   拿B的50.00%: 重量=10, 价值=50.00
#
# 总价值: 270.00

import heapq

def optimal_merge_pattern(files):
    """
    最优合并问题（贪心）
    时间：O(n log n)
    空间：O(n)
    """
    if len(files) < 2:
        return 0

    # 第1步：创建最小堆
    heap = files.copy()
    heapq.heapify(heap)

    print("初始文件:", heap)

    # 第2步：每次合并最小的两个
    total_cost = 0
    step = 1

    while len(heap) > 1:
        # 取出最小的两个
        file1 = heapq.heappop(heap)
        file2 = heapq.heappop(heap)

        # 合并
        merged = file1 + file2
        total_cost += merged

        print(f"\n步骤{step}:")
        print(f"  合并 {file1} 和 {file2} → {merged}")
        print(f"  当前代价: {total_cost}")

        # 放回堆
        heapq.heappush(heap, merged)
        step += 1

    print(f"\n最小总代价: {total_cost}")
    return total_cost

# 测试
print("\n" + "=" * 60)
print("最优合并问题")
print("=" * 60)

files = [1, 2, 3, 4]
print(f"文件大小: {files}")
cost = optimal_merge_pattern(files)

# 输出：
# ============================================================
# 最优合并问题
# ============================================================
# 文件大小: [1, 2, 3, 4]
# 初始文件: [1, 2, 3, 4]
#
# 步骤1:
#   合并 1 和 2 → 3
#   当前代价: 3
#
# 步骤2:
#   合并 3 和 3 → 6
#   当前代价: 9
#
# 步骤3:
#   合并 4 和 6 → 10
#   当前代价: 19
#
# 最小总代价: 19

def can_complete_circuit(gas, cost):
    """
    加油站问题（贪心）
    时间：O(n)
    空间：O(1)
    """
    n = len(gas)

    # 总汽油和总消耗
    total_gas = sum(gas)
    total_cost = sum(cost)

    if total_gas < total_cost:
        print(f"总汽油({total_gas}) < 总消耗({total_cost}), 无法完成")
        return -1

    print(f"总汽油({total_gas}) >= 总消耗({total_cost}), 可能完成\n")

    # 贪心：寻找起点
    start = 0
    current_gas = 0

    print("寻找起点:")
    for i in range(n):
        current_gas += gas[i] - cost[i]
        print(f"  站点{i}: gas={gas[i]}, cost={cost[i]}, 净余={gas[i]-cost[i]}, 当前油量={current_gas}")

        if current_gas < 0:
            # 从i出发失败，从i+1重新开始
            print(f"    × 从{start}出发失败，尝试从{i+1}开始")
            start = i + 1
            current_gas = 0

    print(f"\n✓ 从站点{start}出发可以完成环路")
    return start

# 测试
print("\n" + "=" * 60)
print("加油站问题")
print("=" * 60)

gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]

print(f"gas  = {gas}")
print(f"cost = {cost}\n")

start = can_complete_circuit(gas, cost)

# 输出：
# ============================================================
# 加油站问题
# ============================================================
# gas  = [1, 2, 3, 4, 5]
# cost = [3, 4, 5, 1, 2]
#
# 总汽油(15) >= 总消耗(15), 可能完成
#
# 寻找起点:
#   站点0: gas=1, cost=3, 净余=-2, 当前油量=-2
#     × 从0出发失败，尝试从1开始
#   站点1: gas=2, cost=4, 净余=-2, 当前油量=-2
#     × 从1出发失败，尝试从2开始
#   站点2: gas=3, cost=5, 净余=-2, 当前油量=-2
#     × 从2出发失败，尝试从3开始
#   站点3: gas=4, cost=1, 净余=3, 当前油量=3
#   站点4: gas=5, cost=2, 净余=3, 当前油量=6
#
# ✓ 从站点3出发可以完成环路

def candy(ratings):
    """
    分发糖果（贪心）
    时间：O(n)
    空间：O(n)
    """
    n = len(ratings)
    if n == 0:
        return 0

    # 每个孩子至少1颗
    candies = [1] * n

    print("初始糖果:", candies)

    # 第1步：从左到右
    print("\n从左到右扫描:")
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
            print(f"  孩子{i}评分>{i-1}, 糖果={candies[i]}")

    print("\n中间结果:", candies)

    # 第2步：从右到左
    print("\n从右到左扫描:")
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)
            print(f"  孩子{i}评分>{i+1}, 糖果=max({candies[i]-1}, {candies[i+1]+1})={candies[i]}")

    total = sum(candies)
    print(f"\n最终糖果分配: {candies}")
    print(f"总糖果数: {total}")

    return total

# 测试
print("\n" + "=" * 60)
print("分发糖果")
print("=" * 60)

ratings = [1, 0, 2]
print(f"评分: {ratings}\n")
total = candy(ratings)

# 输出：
# ============================================================
# 分发糖果
# ============================================================
# 评分: [1, 0, 2]
#
# 初始糖果: [1, 1, 1]
#
# 从左到右扫描:
#   孩子1评分>0, 糖果=1  (不满足，因为1>0是false)
#   孩子2评分>1, 糖果=2
#
# 中间结果: [1, 1, 2]
#
# 从右到左扫描:
#   孩子1评分>2, 糖果=max(1, 3)=3  (不满足，因为0>2是false)
#   孩子0评分>1, 糖果=max(1, 2)=2
#
# 最终糖果分配: [2, 1, 2]
# 总糖果数: 5

def wiggle_max_length(nums):
    """
    摆动序列（贪心）
    时间：O(n)
    空间：O(1)
    """
    if len(nums) < 2:
        return len(nums)

    up = 1   # 上升趋势的长度
    down = 1 # 下降趋势的长度

    print("摆动序列分析:")
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:  # 上升
            up = down + 1
            print(f"  位置{i}: {nums[i-1]} → {nums[i]} (上升), up={up}")
        elif nums[i] < nums[i-1]:  # 下降
            down = up + 1
            print(f"  位置{i}: {nums[i-1]} → {nums[i]} (下降), down={down}")

    print(f"\n最长摆动序列长度: {max(up, down)}")
    return max(up, down)

# 测试
print("=" * 60)
print("摆动序列")
print("=" * 60)

nums = [1, 7, 4, 9, 2, 5]
print(f"输入: {nums}\n")
result = wiggle_max_length(nums)

# 输出：6 (整个序列都是摆动)
# 1 < 7 < 4 < 9 < 2 < 5
# ↑   ↓   ↑   ↓   ↑

def monotone_increasing_digits(N):
    """
    单调递增的数字（贪心）
    时间：O(log N)
    空间：O(log N)
    """
    digits = list(str(N))
    n = len(digits)

    print(f"输入: {N}")
    print(f"数字: {digits}")

    # 从左到右找到第一个递减的位置
    marker = n
    for i in range(n-1, 0, -1):
        if digits[i] < digits[i-1]:
            marker = i
            digits[i-1] = str(int(digits[i-1]) - 1)
            print(f"  位置{i-1}: {digits[i-1]} > {digits[i]}, 减小前一位")

    # marker之后全部设为9
    for i in range(marker, n):
        digits[i] = '9'

    result = int(''.join(digits))
    print(f"结果: {result}")
    return result

# 测试
print("\n" + "=" * 60)
print("单调递增的数字")
print("=" * 60)

N = 332
result = monotone_increasing_digits(N)
# 输出：299

def can_place_flowers(flowerbed, n):
    """
    种花问题（贪心）
    时间：O(n)
    空间：O(1)
    """
    count = 0
    length = len(flowerbed)

    print("花坛:", flowerbed)
    print("尝试种花:\n")

    for i in range(length):
        if flowerbed[i] == 0:
            # 检查前后是否都是0
            empty_left = (i == 0) or (flowerbed[i-1] == 0)
            empty_right = (i == length-1) or (flowerbed[i+1] == 0)

            if empty_left and empty_right:
                flowerbed[i] = 1
                count += 1
                print(f"  位置{i}: ✓ 可以种花")

                if count >= n:
                    print(f"\n已种够{n}朵花")
                    return True
            else:
                print(f"  位置{i}: ✗ 不能种花 (前后有花)")

    print(f"\n最多只能种{count}朵花")
    return count >= n

# 测试
print("\n" + "=" * 60)
print("种花问题")
print("=" * 60)

flowerbed = [1, 0, 0, 0, 1]
n = 1
print(f"花坛: {flowerbed}, 需要种{n}朵\n")
result = can_place_flowers(flowerbed, n)

# 输出：True