06-贪心算法

💡 核心结论

贪心本质

  • 定义：每步选择当前最优，期望全局最优

  • 关键：局部最优 → 全局最优（需要证明）

  • vs DP：贪心不回头，DP考虑所有可能

  • 难点：如何证明贪心策略正确

  • 应用：区间调度、哈夫曼编码、最小生成树

贪心 vs 动态规划

特性

贪心

动态规划

决策

当前最优

全局最优

回溯

不回溯

可回溯

子问题

无重叠

有重叠

时间

通常O(n log n)

O(n²)或更高

正确性

需要证明

一定正确

贪心策略

  1. 排序：按某种规则排序后贪心选择

  2. 优先队列：每次选择最优元素

  3. 局部最优：证明局部最优能导致全局最优

经典问题

  • 区间调度：按结束时间排序

  • 跳跃游戏：维护最远距离

  • 加油站：从能到达最远的开始

  • 分配问题：排序后贪心分配

🎯 经典贪心问题

1. 区间调度

def interval_scheduling(intervals):
    """最多不重叠区间数"""
    if not intervals:
        return 0
    
    # 按结束时间排序
    intervals.sort(key=lambda x: x[1])
    
    count = 1
    end = intervals[0][1]
    
    for i in range(1, len(intervals)):
        if intervals[i][0] >= end:
            count += 1
            end = intervals[i][1]
    
    return count

2. 跳跃游戏

def can_jump(nums):
    """能否跳到最后"""
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    return True

def jump(nums):
    """最少跳跃次数"""
    jumps = 0
    curr_end = 0
    max_reach = 0
    
    for i in range(len(nums) - 1):
        max_reach = max(max_reach, i + nums[i])
        if i == curr_end:
            jumps += 1
            curr_end = max_reach
    
    return jumps

3. 分配饼干

def find_content_children(g, s):
    """g:孩子胃口 s:饼干大小"""
    g.sort()
    s.sort()
    
    child = cookie = 0
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1
        cookie += 1
    
    return child

📚 LeetCode练习

💻 完整代码实现

Python 实现

  1"""
  2贪心算法实现
  3"""
  4
  5import heapq
  6
  7# ========== 区间调度 ==========
  8
  9def interval_scheduling(intervals):
 10    """最多不重叠区间数"""
 11    if not intervals:
 12        return 0
 13    
 14    intervals.sort(key=lambda x: x[1])  # 按结束时间排序
 15    
 16    count = 1
 17    end = intervals[0][1]
 18    
 19    for i in range(1, len(intervals)):
 20        if intervals[i][0] >= end:
 21            count += 1
 22            end = intervals[i][1]
 23    
 24    return count
 25
 26
 27# ========== 跳跃游戏 ==========
 28
 29def can_jump(nums):
 30    """能否跳到最后"""
 31    max_reach = 0
 32    
 33    for i in range(len(nums)):
 34        if i > max_reach:
 35            return False
 36        max_reach = max(max_reach, i + nums[i])
 37    
 38    return True
 39
 40
 41def jump(nums):
 42    """最少跳跃次数"""
 43    jumps = 0
 44    curr_end = 0
 45    max_reach = 0
 46    
 47    for i in range(len(nums) - 1):
 48        max_reach = max(max_reach, i + nums[i])
 49        
 50        if i == curr_end:
 51            jumps += 1
 52            curr_end = max_reach
 53    
 54    return jumps
 55
 56
 57# ========== 分配饼干 ==========
 58
 59def find_content_children(g, s):
 60    """g:孩子胃口 s:饼干大小"""
 61    g.sort()
 62    s.sort()
 63    
 64    child = cookie = 0
 65    
 66    while child < len(g) and cookie < len(s):
 67        if s[cookie] >= g[child]:
 68            child += 1
 69        cookie += 1
 70    
 71    return child
 72
 73
 74# ========== 买卖股票II ==========
 75
 76def max_profit(prices):
 77    """可多次买卖"""
 78    profit = 0
 79    
 80    for i in range(1, len(prices)):
 81        if prices[i] > prices[i-1]:
 82            profit += prices[i] - prices[i-1]
 83    
 84    return profit
 85
 86
 87# ========== 加油站 ==========
 88
 89def can_complete_circuit(gas, cost):
 90    """能否环绕一圈"""
 91    total_tank = 0
 92    curr_tank = 0
 93    start = 0
 94    
 95    for i in range(len(gas)):
 96        total_tank += gas[i] - cost[i]
 97        curr_tank += gas[i] - cost[i]
 98        
 99        if curr_tank < 0:
100            start = i + 1
101            curr_tank = 0
102    
103    return start if total_tank >= 0 else -1
104
105
106# ========== 分发糖果 ==========
107
108def candy(ratings):
109    """每个孩子至少一个糖，评分高的比邻居多"""
110    n = len(ratings)
111    candies = [1] * n
112    
113    # 从左到右
114    for i in range(1, n):
115        if ratings[i] > ratings[i-1]:
116            candies[i] = candies[i-1] + 1
117    
118    # 从右到左
119    for i in range(n - 2, -1, -1):
120        if ratings[i] > ratings[i+1]:
121            candies[i] = max(candies[i], candies[i+1] + 1)
122    
123    return sum(candies)
124
125
126# ========== 任务调度器 ==========
127
128def least_interval(tasks, n):
129    """任务调度最短时间"""
130    from collections import Counter
131    
132    task_counts = Counter(tasks)
133    max_count = max(task_counts.values())
134    max_count_tasks = sum(1 for count in task_counts.values() if count == max_count)
135    
136    # 计算最短时间
137    intervals = (max_count - 1) * (n + 1) + max_count_tasks
138    
139    return max(intervals, len(tasks))
140
141
142def demo():
143    """演示贪心算法"""
144    print("=== 贪心算法演示 ===\n")
145    
146    # 区间调度
147    intervals = [[1,3], [2,4], [3,5], [1,2]]
148    print(f"区间调度 {intervals}:")
149    print(f"  最多不重叠区间: {interval_scheduling(intervals)}\n")
150    
151    # 跳跃游戏
152    nums = [2,3,1,1,4]
153    print(f"跳跃游戏 {nums}:")
154    print(f"  能否跳到最后: {can_jump(nums)}")
155    print(f"  最少跳跃次数: {jump(nums)}\n")
156    
157    # 分配饼干
158    g, s = [1,2,3], [1,1]
159    print(f"分配饼干 g={g}, s={s}:")
160    print(f"  满足孩子数: {find_content_children(g, s)}\n")
161    
162    # 买卖股票
163    prices = [7,1,5,3,6,4]
164    print(f"买卖股票II {prices}:")
165    print(f"  最大利润: {max_profit(prices)}\n")
166    
167    # 加油站
168    gas = [1,2,3,4,5]
169    cost = [3,4,5,1,2]
170    print(f"加油站 gas={gas}, cost={cost}:")
171    print(f"  起始站: {can_complete_circuit(gas, cost)}\n")
172    
173    # 分发糖果
174    ratings = [1,0,2]
175    print(f"分发糖果 {ratings}:")
176    print(f"  最少糖果数: {candy(ratings)}")
177
178
179if __name__ == '__main__':
180    demo()
181

C++ 实现

  1/**
  2 * 贪心算法实现
  3 */
  4
  5#include <iostream>
  6#include <vector>
  7#include <algorithm>
  8
  9using namespace std;
 10
 11// 区间调度
 12int intervalScheduling(vector<vector<int>>& intervals) {
 13    if (intervals.empty()) return 0;
 14    
 15    // 按结束时间排序
 16    sort(intervals.begin(), intervals.end(), 
 17         [](const vector<int>& a, const vector<int>& b) {
 18             return a[1] < b[1];
 19         });
 20    
 21    int count = 1;
 22    int end = intervals[0][1];
 23    
 24    for (int i = 1; i < intervals.size(); i++) {
 25        if (intervals[i][0] >= end) {
 26            count++;
 27            end = intervals[i][1];
 28        }
 29    }
 30    
 31    return count;
 32}
 33
 34// 跳跃游戏
 35bool canJump(const vector<int>& nums) {
 36    int maxReach = 0;
 37    
 38    for (int i = 0; i < nums.size(); i++) {
 39        if (i > maxReach) {
 40            return false;
 41        }
 42        maxReach = max(maxReach, i + nums[i]);
 43    }
 44    
 45    return true;
 46}
 47
 48int jump(const vector<int>& nums) {
 49    int jumps = 0;
 50    int currEnd = 0;
 51    int maxReach = 0;
 52    
 53    for (int i = 0; i < nums.size() - 1; i++) {
 54        maxReach = max(maxReach, i + nums[i]);
 55        
 56        if (i == currEnd) {
 57            jumps++;
 58            currEnd = maxReach;
 59        }
 60    }
 61    
 62    return jumps;
 63}
 64
 65// 分配饼干
 66int findContentChildren(vector<int>& g, vector<int>& s) {
 67    sort(g.begin(), g.end());
 68    sort(s.begin(), s.end());
 69    
 70    int child = 0, cookie = 0;
 71    
 72    while (child < g.size() && cookie < s.size()) {
 73        if (s[cookie] >= g[child]) {
 74            child++;
 75        }
 76        cookie++;
 77    }
 78    
 79    return child;
 80}
 81
 82// 买卖股票II
 83int maxProfit(const vector<int>& prices) {
 84    int profit = 0;
 85    
 86    for (int i = 1; i < prices.size(); i++) {
 87        if (prices[i] > prices[i-1]) {
 88            profit += prices[i] - prices[i-1];
 89        }
 90    }
 91    
 92    return profit;
 93}
 94
 95// 加油站
 96int canCompleteCircuit(const vector<int>& gas, const vector<int>& cost) {
 97    int totalTank = 0;
 98    int currTank = 0;
 99    int start = 0;
100    
101    for (int i = 0; i < gas.size(); i++) {
102        totalTank += gas[i] - cost[i];
103        currTank += gas[i] - cost[i];
104        
105        if (currTank < 0) {
106            start = i + 1;
107            currTank = 0;
108        }
109    }
110    
111    return totalTank >= 0 ? start : -1;
112}
113
114// 分发糖果
115int candy(const vector<int>& ratings) {
116    int n = ratings.size();
117    vector<int> candies(n, 1);
118    
119    // 从左到右
120    for (int i = 1; i < n; i++) {
121        if (ratings[i] > ratings[i-1]) {
122            candies[i] = candies[i-1] + 1;
123        }
124    }
125    
126    // 从右到左
127    for (int i = n - 2; i >= 0; i--) {
128        if (ratings[i] > ratings[i+1]) {
129            candies[i] = max(candies[i], candies[i+1] + 1);
130        }
131    }
132    
133    int sum = 0;
134    for (int c : candies) sum += c;
135    return sum;
136}
137
138int main() {
139    cout << "=== 贪心算法演示 ===" << endl << endl;
140    
141    // 区间调度
142    vector<vector<int>> intervals = {{1,3}, {2,4}, {3,5}, {1,2}};
143    cout << "区间调度 [[1,3],[2,4],[3,5],[1,2]]:" << endl;
144    cout << "  最多不重叠区间: " << intervalScheduling(intervals) << endl << endl;
145    
146    // 跳跃游戏
147    vector<int> nums = {2,3,1,1,4};
148    cout << "跳跃游戏 [2,3,1,1,4]:" << endl;
149    cout << "  能否跳到最后: " << (canJump(nums) ? "是" : "否") << endl;
150    cout << "  最少跳跃次数: " << jump(nums) << endl << endl;
151    
152    // 分配饼干
153    vector<int> g = {1,2,3};
154    vector<int> s = {1,1};
155    cout << "分配饼干 g=[1,2,3], s=[1,1]:" << endl;
156    cout << "  满足孩子数: " << findContentChildren(g, s) << endl << endl;
157    
158    // 买卖股票
159    vector<int> prices = {7,1,5,3,6,4};
160    cout << "买卖股票II [7,1,5,3,6,4]:" << endl;
161    cout << "  最大利润: " << maxProfit(prices) << endl << endl;
162    
163    // 加油站
164    vector<int> gas = {1,2,3,4,5};
165    vector<int> cost = {3,4,5,1,2};
166    cout << "加油站 gas=[1,2,3,4,5], cost=[3,4,5,1,2]:" << endl;
167    cout << "  起始站: " << canCompleteCircuit(gas, cost) << endl << endl;
168    
169    // 分发糖果
170    vector<int> ratings = {1,0,2};
171    cout << "分发糖果 [1,0,2]:" << endl;
172    cout << "  最少糖果数: " << candy(ratings) << endl;
173    
174    return 0;
175}