贪心算法

核心思想

每一步做当前看起来最好的选择，不回溯，不 DP。

能用贪心解决的问题必须满足：
1. 贪心选择性质：局部最优 → 全局最优
2. 最优子结构：子问题的最优解包含在全局最优中

⚠️ 贪心不总是正确 — 错误场景：
  硬币面额 [1, 3, 4]，找零 6
  贪心: 4+1+1 = 3 枚
  最优: 3+3 = 2 枚 ❌

区间调度（活动选择）

// 给定 n 个区间 [start, end]，选最多的不重叠区间
int maxNonOverlap(vector<pair<int,int>> &intervals) {
    // 按结束时间排序（贪心：最早结束的先选）
    sort(intervals.begin(), intervals.end(),
         [](auto &a, auto &b) { return a.second < b.second; });

    int count = 0, lastEnd = INT_MIN;
    for (auto [s, e] : intervals) {
        if (s >= lastEnd) {
            ++count;
            lastEnd = e;
        }
    }
    return count;
}
// 时间 O(n log n)，空间 O(1)

// 变体：最少箭射爆气球 = 合并重叠区间
int minArrows(vector<pair<int,int>> &points) {
    sort(points.begin(), points.end(),
         [](auto &a, auto &b) { return a.second < b.second; });
    int arrows = 0;
    long long last = LLONG_MIN;
    for (auto [s, e] : points)
        if (s > last) { ++arrows; last = e; }
    return arrows;
}

Huffman 编码

// 构建最优前缀码，最小化加权路径长度
struct Node { int freq; Node *left, *right; };

Node *buildHuffman(const vector<int> &freqs) {
    // 小顶堆，按频率排序
    auto cmp = [](Node *a, Node *b) { return a->freq > b->freq; };
    priority_queue<Node *, vector<Node *>, decltype(cmp)> pq(cmp);

    for (int f : freqs) pq.push(new Node{f, nullptr, nullptr});

    while (pq.size() > 1) {
        auto *left = pq.top(); pq.pop();
        auto *right = pq.top(); pq.pop();
        pq.push(new Node{left->freq + right->freq, left, right});
    }
    return pq.top();
}
// 时间 O(n log n)

跳跃游戏

// [2,3,1,1,4] → true（从索引 0 可以跳到末尾）
bool canJump(const vector<int> &nums) {
    int farthest = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (i > farthest) return false;   // 当前位置不可达
        farthest = max(farthest, i + nums[i]);
    }
    return true;
}
// 时间 O(n)，空间 O(1)
// 贪心核心：每一步维护"最远可达位置"

加油站问题

// gas=[1,2,3,4,5], cost=[3,4,5,1,2] → 从索引 3 出发可绕一圈
int canCompleteCircuit(const vector<int> &gas, const vector<int> &cost) {
    int total = 0, cur = 0, start = 0;
    for (int i = 0; i < gas.size(); ++i) {
        int diff = gas[i] - cost[i];
        total += diff;
        cur += diff;
        if (cur < 0) {        // 从 start 到 i 无法走完
            start = i + 1;    // 尝试从下一个开始
            cur = 0;
        }
    }
    return total >= 0 ? start : -1;
}

贪心 vs DP

	贪心	DP
决策	只看当前最优	考虑所有子问题
回溯	不回溯	记录所有状态
时间复杂度	通常 O(n log n)	通常 O(n²) 或更高
正确性	需要证明	自然正确

判断能否贪心：尝试举反例。如果能找到贪心失效的例子，就必须用 DP。