前言

贪心（Greedy）是五大基础算法思想之一，逻辑简单、时间复杂度极低（大多 O (n) / O (nlogn)），笔试、面试高频考点。 很多初学者只会套模板，分不清什么时候能用贪心、贪心策略怎么推导，本文从零拆解：核心定义、适用条件、解题通用步骤、区分贪心 / 动态规划，搭配简单入门→中等进阶→困难高频共 10 道经典 LeetCode 原题，每道题含题意、贪心思路、完整 Java 代码、复杂度分析、易错点，看完可直接刷题、面试复盘。

一、贪心算法核心基础

1. 核心思想

每一步只做当前局部最优选择，不回头、不回溯、不预判未来，依靠不断累积局部最优，最终得到全局最优解。 特点：短视、无回溯、只看当下最优，执行效率远高于动态规划。

2. 两大必备使用条件（缺一不可）

只有同时满足下面两点，贪心才能求出全局最优，否则只能局部最优，答案错误。

1. 贪心选择性质 当前局部最优决策，不会阻断后续全局最优解；每一步最优可以独立做出，无需依赖后续状态。
2. 最优子结构 全局最优解，一定包含子问题的最优解；拆分子问题单独求解不影响整体结果。

3. 贪心 vs 动态规划（关键区分）

表格

维度	贪心算法	动态规划 DP
决策方式	每一步固定选局部最优，不回头	记录所有子问题解，遍历所有选择
是否回溯	无，决策不可逆	可回溯，缓存子问题结果
时间复杂度	O (nlogn)、O (n)，极快	O (n²)、O (nk)，开销更大
适用场景	区间、分配、跳跃、股票、找零	01 背包、最长子序列、路径规划
核心矛盾	局部最优能否推全局最优	存在多种选择，需要对比所有方案

举例：01 背包不能用贪心（物品不可拆分），部分背包（物品可分割）可以贪心；这是判断贪心能否使用的经典例子。

4. 贪心通用解题四步法

1. 拆解问题：把大问题拆成一步步独立的子步骤；
2. 推导贪心策略：找到每一步 “局部最优” 的判断标准（排序规则、取值规则）；
3. 验证合法性：简单举反例，确认局部最优不会导致全局出错；
4. 编码实现：排序 + 一次线性遍历，统计结果。

5. 常见贪心策略分类（刷题归类）

1. 分配类：分发饼干、柠檬水找零、分糖果；
2. 区间类：无重叠区间、区间选点、活动安排；
3. 跳跃覆盖类：跳跃游戏、跳跃游戏 II；
4. 股票交易类：无限次买卖股票；
5. 数组极值类：K 次取反最大和、加油站；
6. 高级贪心：双维度排序（排队、哈夫曼树）。

二、入门简单题（2 道，理解基础贪心逻辑）

例题 1：455. 分发饼干（LeetCode 简单）

题意

孩子数组g：每个孩子胃口；饼干数组s：每块饼干大小。 饼干尺寸≥孩子胃口才能满足，求最多满足多少孩子。

贪心策略

1. 两个数组从小到大排序；
2. 最小饼干优先匹配最小胃口，不浪费大饼干，局部最优→全局最多孩子。

Java 完整代码

java

import java.util.Arrays;
public class Solution455 {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int child = 0; // 孩子指针
        int cookie = 0;// 饼干指针
        while (child < g.length && cookie < s.length) {
            // 当前饼干能满足孩子
            if (s[cookie] >= g[child]) {
                child++;
            }
            cookie++;
        }
        return child;
    }
}

复杂度

排序 O (nlogn + mlogm)，遍历 O (n+m)；空间 O (1)。

例题 2：860. 柠檬水找零（LeetCode 简单）

题意

柠檬水 5 元一杯，顾客只会付 5/10/20 元，按顺序排队，判断能否正确找零。

贪心策略

1. 收到 20 元：优先用 10+5（10 元面额稀缺，留 5 元应对更多 10 元顾客）；
2. 收到 10 元：必须找一张 5 元；
3. 收到 5 元：直接留存；

Java 完整代码

java

public class Solution860 {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int money : bills) {
            if (money == 5) {
                five++;
            } else if (money == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else {
                // 20元，优先10+5
                if (ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

易错点

20 元优先消耗 10 元，不能直接三张 5，否则后续 10 元顾客无法找零。

三、中等经典必刷题（6 道，面试核心）

例题 3：122. 买卖股票的最佳时机 II（股票贪心）

题意

股价数组，可无限次买卖，不能同时持有多只股票，求最大利润。

贪心策略

只要后一天价格 > 前一天，当天买入次日卖出，累加所有正向差值。 逻辑等价：拆分所有上涨区间，每一段都赚差价。

Java 代码

java

public class Solution122 {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

例题 4：435. 无重叠区间（区间贪心模板）

题意

二维数组存放区间起止，求最少移除多少区间，让剩余区间互不重叠。

贪心策略（区间通用模板）

1. 按区间右端点升序排序；
2. 每次选结束最早的区间，留出更多空间给后续区间，容纳最多不重叠区间；
3. 总区间数 - 最多不重叠区间 = 需要删除数量。

Java 代码

java

import java.util.Arrays;
public class Solution435 {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        // 按右端点升序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int count = 1;
        int lastEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            int start = intervals[i][0];
            if (start >= lastEnd) {
                count++;
                lastEnd = intervals[i][1];
            }
        }
        return intervals.length - count;
    }
}

区间类通用套路

求最多不重叠区间 → 按右端点排序； 区间覆盖 → 按左端点排序。

例题 5：55. 跳跃游戏（可达性贪心）

题意

数组每个元素代表当前位置最大跳跃距离，判断能否跳到数组最后一位。

贪心策略

遍历数组，持续维护当前能到达的最远距离 maxReach； 如果当前下标 i > maxReach，说明无法到达该位置，直接 false； 遍历结束 maxReach 覆盖末尾则 true。

Java 代码

java

public class Solution55 {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (i > maxReach) return false;
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= len - 1) return true;
        }
        return true;
    }
}

例题 6：45. 跳跃游戏 II（最小步数贪心，高频面试）

题意

数组代表最大跳跃距离，保证一定能到达末尾，求最少跳跃次数。

贪心策略（边界跳跃）

1. curMax：当前这一跳能到达的最远距离；
2. nextMax：下一跳能到达的最远距离；
3. 遍历到 curMax 边界时，必须起跳一次，更新 curMax 为 nextMax。

Java 代码

java

public class Solution45 {
    public int jump(int[] nums) {
        int len = nums.length;
        if (len == 1) return 0;
        int step = 0;
        int curMax = 0;
        int nextMax = 0;
        for (int i = 0; i < len - 1; i++) {
            nextMax = Math.max(nextMax, i + nums[i]);
            // 到达当前边界，必须跳一次
            if (i == curMax) {
                step++;
                curMax = nextMax;
                if (curMax >= len - 1) break;
            }
        }
        return step;
    }
}

例题 7：1005. K 次取反后最大化的数组和

题意

数组可翻转数字符号，最多翻转 K 次，同一数字可多次翻转，求数组最大和。

贪心策略

1. 数组升序排序，优先翻转负数（把负数变正数收益最大）；
2. K 用完直接求和；
3. K 剩余且为奇数：最小正数翻转一次（总和减去两倍最小值）。

Java 代码

java

import java.util.Arrays;
public class Solution1005 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        // 翻转负数
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            } else break;
        }
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            sum += num;
            min = Math.min(min, num);
        }
        // 剩余奇数次翻转，减去两倍最小值
        if (k % 2 == 1) sum -= 2 * min;
        return sum;
    }
}

例题 8：134. 加油站（环形贪心）

题意

环形路线，gas [i] 是加油站油量，cost [i] 开到下一站消耗；判断是否存在起点绕环一周，返回起点下标。

贪心策略

1. 总油量 < 总消耗 → 直接无解；
2. 遍历累加当前剩余油量，若剩余 < 0，起点更新为下一站，清空累计油量。

Java 代码

java

public class Solution134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0;
        int curOil = 0;
        int start = 0;
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            curOil += gas[i] - cost[i];
            // 当前起点无法走到i，起点改为i+1
            if (curOil < 0) {
                curOil = 0;
                start = i + 1;
            }
        }
        return totalGas >= totalCost ? start : -1;
    }
}

四、困难进阶题（2 道，大厂面试拔高）

例题 9：135. 分发糖果（双向两次贪心）

题意

一排孩子，每个有评分，规则：

1. 每个孩子至少 1 颗糖；
2. 评分更高的孩子，糖果比相邻孩子多；求最少糖果总数。

贪心策略（单向贪心无法满足双向约束，两次扫描）

1. 左→右遍历：如果右孩子分数 > 左，糖果 = 左糖果 + 1；
2. 右→左遍历：如果左孩子分数 > 右，且糖果≤右，糖果 = 右糖果 + 1；

Java 代码

java

public class Solution135 {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candy = new int[n];
        // 初始每人1颗
        for (int i = 0; i < n; i++) candy[i] = 1;
        // 左到右
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }
        // 右到左
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]) {
                candy[i] = candy[i + 1] + 1;
            }
        }
        int sum = 0;
        for (int num : candy) sum += num;
        return sum;
    }
}

例题 10：区间选点（经典贪心模板，蓝桥高频）

题意

给定若干区间，选择最少的点，让每个区间至少包含一个点。

贪心策略

按右端点升序，每次选当前区间右端点，跳过所有包含该点的区间。

Java 代码

java

import java.util.Arrays;
public class RangePoint {
    public static int minPoint(int[][] ranges) {
        Arrays.sort(ranges, (a, b) -> a[1] - b[1]);
        int res = 0;
        int lastPoint = Integer.MIN_VALUE;
        for (int[] range : ranges) {
            int l = range[0], r = range[1];
            if (l > lastPoint) {
                res++;
                lastPoint = r;
            }
        }
        return res;
    }
}

五、贪心算法常见坑点总结

1. 不验证贪心策略直接写代码 很多问题局部最优无法推全局，例如 01 背包用贪心直接出错，必须先举反例验证。
2. 区间排序规则选错 求最多不重叠区间按右端点；区间覆盖按左端点；排序规则错答案完全错误。
3. 双向约束只用一次贪心 分发糖果、排队打水这类左右互相影响的题目，单次遍历无法满足条件，需要两次扫描。
4. 数值边界忽略负数、极值 K 次取反、加油站题目容易忽略全负数、总和不足边界。
5. 跳跃游戏混淆可达性与最小步数 55 题只维护最远可达；45 题需要记录起跳边界，两套逻辑不能混用。

六、贪心刷题分类总结（刷题顺序）

1. 分配入门：分发饼干、柠檬水找零（建立贪心直觉）
2. 数组极值：K 次取反、加油站、股票 II（一维线性贪心）
3. 区间系列：无重叠区间、区间选点（排序贪心核心模板）
4. 跳跃覆盖：跳跃游戏、跳跃游戏 II（边界贪心，面试高频）
5. 双向复杂贪心：分发糖果（两次扫描，拔高题）

七、学习路线与面试考点

学习顺序

1. 理解贪心两大使用条件，区分贪心与 DP；
2. 刷简单分配类，掌握排序 + 一次遍历基础模板；
3. 专攻区间类题目，吃透排序规则；
4. 跳跃、股票、加油站一维线性贪心；
5. 双向扫描、多维度排序困难题。

面试高频提问

1. 贪心和动态规划区别，什么时候不能用贪心？
2. 区间调度为什么按右端点排序？换左端点会有什么问题？
3. 跳跃游戏 II 最小步数贪心思路怎么证明？
4. 分发糖果为什么需要两次遍历，一次遍历行不行？
5. 01 背包为什么不能贪心，部分背包可以？

结语

贪心算法是性价比最高的算法思想，代码简短、性能优秀，绝大多数场景只需要排序 + 单次线性遍历。核心难点不在于编码，而是推导正确的局部最优策略，刷题时不要直接抄代码，先手动模拟贪心选择过程，验证策略正确性。 后端、算法笔试、蓝桥杯、LeetCode 热题中贪心占比极高，熟练掌握本文 10 道例题，可覆盖 90% 贪心面试场景。