编程进阶网
杨充
2017-07-17
目录

贪心算法题合集

# 跳跃游戏（Jump Game）

LeetCode 55 · ⭐⭐ · 贪心

# 01. 题目

数组每个元素表示最大跳跃长度。判断能否从0跳到末尾。[2,3,1,1,4] → true。

# 02. 题目分析

flowchart TD
    A["reach = 0"] --> B["i=0..n-1"]
    B --> C{"i > reach ?"}
    C -->|YES| D["不可达 → false"]
    C -->|NO| E["reach = max(reach, i+nums[i])"]
    E --> B
    B -->|遍历完| F["true"]
1
2
3
4
5
6
7

贪心选择：每一步维护"当前能到达的最远位置"。若 i > reach 说明跳不到 i。

nums=[2,3,1,1,4]
i=0: reach=max(0,0+2)=2
i=1: reach=max(2,1+3)=4 ≥ n-1 → true
1
2
3

# 03. 代码

Java：

public boolean canJump(int[] nums) {
    int reach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > reach) return false;
        reach = Math.max(reach, i + nums[i]);
    }
    return true;
}
1
2
3
4
5
6
7
8

Python：

def canJump(self, nums):
    reach = 0
    for i, n in enumerate(nums):
        if i > reach: return False
        reach = max(reach, i + n)
    return True
1
2
3
4
5
6

C++：

bool canJump(vector<int>& nums) {
    int reach=0;
    for(int i=0;i<nums.size();i++){ if(i>reach) return false; reach=max(reach,i+nums[i]); }
    return true;
}
1
2
3
4
5

复杂度：O(N)/O(1)。

# 04. 总结

核心 说明
reach 维护当前能到达的最远下标
i > reach 无法到达当前位置→失败
贪心正确性 每次都选能跳最远的

相关：150 跳跃II

# 跳跃游戏 II（Jump Game II）

LeetCode 45 · ⭐⭐ · 贪心

# 01. 题目

求最少跳跃次数到达末尾。[2,3,1,1,4] → 2（0→1→4）。

# 02. 题目分析

flowchart TD
    A["jumps=0, curEnd=0, farthest=0"] --> B["i=0..n-2"]
    B --> C["farthest = max(farthest, i+nums[i])"]
    C --> D{"i == curEnd ?"}
    D -->|YES| E["jumps++; curEnd = farthest"]
    D -->|NO| F["继续"]
    E --> B
1
2
3
4
5
6
7

curEnd：当前跳跃能覆盖的最远边界。当 i 到达 curEnd 时，必须再跳一次。

nums=[2,3,1,1,4]
i=0: farthest=2, i==curEnd(0) → jumps=1, curEnd=2
i=1: farthest=4, i≠curEnd → 继续
i=2: farthest=4, i==curEnd(2) → jumps=2, curEnd=4 ≥ n-1 → 结束
1
2
3
4

# 03. 代码

Java：

public int jump(int[] nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) { jumps++; curEnd = farthest; }
    }
    return jumps;
}
1
2
3
4
5
6
7
8

Python：

def jump(self, nums):
    jumps = cur_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end: jumps += 1; cur_end = farthest
    return jumps
1
2
3
4
5
6

C++：

int jump(vector<int>& nums) {
    int jumps=0, curEnd=0, farthest=0;
    for(int i=0;i<nums.size()-1;i++){ farthest=max(farthest,i+nums[i]); if(i==curEnd){ jumps++; curEnd=farthest; } }
    return jumps;
}
1
2
3
4
5

复杂度：O(N)/O(1)。

# 04. L001 vs L002

L001 能否到达 L002 最少步数
返回值 bool int
关键变量 reach jumps+curEnd+farthest
额外条件 — i==curEnd 触发跳跃

相关：149 跳跃游戏

# 分发饼干（Assign Cookies）

LeetCode 455 · ⭐ · 排序+贪心

# 01. 题目

每个孩子有胃口 g[i]，每块饼干有大小 s[j]。s[j]≥g[i] 时满足该孩子。最多满足几个？

g=[1,2,3], s=[1,1] → 1。

# 02. 题目分析

flowchart TD
    A["排序g和s"] --> B["双指针: i(孩子), j(饼干)"]
    B --> C{"s[j] >= g[i] ?"}
    C -->|YES| D["i++(满足一个)"]
    C --> E["j++(饼干尝试下一个)"]
    D & E --> B
1
2
3
4
5
6

贪心策略：最小饼干满足最小胃口的孩子。

# 03. 代码

Java：

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g); Arrays.sort(s);
    int i = 0;
    for (int j = 0; i < g.length && j < s.length; j++)
        if (s[j] >= g[i]) i++;
    return i;
}
1
2
3
4
5
6
7

Python：

def findContentChildren(self, g, s):
    g.sort(); s.sort(); i = 0
    for x in s:
        if i < len(g) and x >= g[i]: i += 1
    return i
1
2
3
4
5

C++：

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(),g.end()); sort(s.begin(),s.end());
    int i=0; for(int j=0;i<g.size()&&j<s.size();j++) if(s[j]>=g[i]) i++;
    return i;
}
1
2
3
4
5

复杂度：O(NlogN)/O(1)。

# 04. 总结

贪心核心：排序 → 最小匹配最小。O(NlogN)。

相关：154 合并区间

# 无重叠区间（Non-overlapping Intervals）

LeetCode 435 · ⭐⭐ · 区间调度贪心

# 01. 题目

最少移除几个区间使剩余不重叠。[[1,2],[2,3],[3,4],[1,3]] → 1（移除[1,3]）。

# 02. 题目分析

flowchart TD
    A["按 end 排序"] --> B["end=intervals[0][1]"]
    B --> C["遍历i=1..n-1"]
    C --> D{"start < end ?"}
    D -->|YES| E["重叠 → remove++"]
    D -->|NO| F["不重叠 → end = intervals[i][1]"]
    E & F --> C
1
2
3
4
5
6
7

为什么按 end 排序？ 选择最早结束的区间，为后面的区间留下最多空间——这是区间调度问题的标准贪心策略。

# 03. 代码

Java：

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int end = intervals[0][1], remove = 0;
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < end) remove++;
        else end = intervals[i][1];
    }
    return remove;
}
1
2
3
4
5
6
7
8
9

Python：

def eraseOverlapIntervals(self, intervals):
    intervals.sort(key=lambda x: x[1])
    end, cnt = intervals[0][1], 0
    for s, e in intervals[1:]:
        if s < end: cnt += 1
        else: end = e
    return cnt
1
2
3
4
5
6
7

C++：

int eraseOverlapIntervals(vector<vector<int>>& ins) {
    sort(ins.begin(),ins.end(),[](auto&a,auto&b){return a[1]<b[1];});
    int end=ins[0][1],cnt=0;
    for(int i=1;i<ins.size();i++){ if(ins[i][0]<end) cnt++; else end=ins[i][1]; }
    return cnt;
}
1
2
3
4
5
6

复杂度：O(NlogN)/O(1)。

# 04. 区间三题对比

无重叠(152) 引爆气球(153) 合并区间(154)
排序 end end start
条件 start < end start > end start <= end
操作 跳过计数 新箭 合并取max end

核心：L152/L153 按 end 贪心，L154 按 start 排以便从前向后合并。

相关：153 引爆气球、154 合并区间

# 用最少数量的箭引爆气球（Minimum Arrows）

LeetCode 452 · ⭐⭐ · 贪心区间

# 01. 题目

[[10,16],[2,8],[1,6],[7,12]] → 2（x=6和x=11各一箭）。气球边界接触也算引爆。

# 02. 分析

与 L152 同框架，但重叠定义不同：start > end 才需新箭。

public int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1])); // 防溢出
    int end = points[0][1], arrows = 1;
    for (int i = 1; i < points.length; i++)
        if (points[i][0] > end) { arrows++; end = points[i][1]; }
    return arrows;
}
1
2
3
4
5
6
7

Python：

def findMinArrowShots(self, points):
    points.sort(key=lambda x: x[1])
    end, arrows = points[0][1], 1
    for s, e in points[1:]:
        if s > end: arrows += 1; end = e
    return arrows
1
2
3
4
5
6

注意：Integer.compare 防溢出（[[Integer.MIN_VALUE, Integer.MAX_VALUE]]）。

复杂度：O(NlogN)/O(1)。

相关：152 无重叠区间

# 合并区间（Merge Intervals）

LeetCode 56 · ⭐⭐ · 排序+贪心

# 01. 题目

[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]

# 02. 分析

flowchart TD
    A["按 start 排序"] --> B["初始化 res = [intervals[0]]"]
    B --> C["遍历剩余"]
    C --> D{"start <= res[-1].end ?"}
    D -->|YES| E["合并: res[-1].end = max(end)"]
    D -->|NO| F["新增区间"]
1
2
3
4
5
6

与 L152/L153 不同：按 start 排序（不是 end），因为需要从前向后合并。

# 03. 代码

Java：

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> res = new ArrayList<>();
    for (int[] in : intervals) {
        if (res.isEmpty() || res.get(res.size() - 1)[1] < in[0])
            res.add(in);
        else
            res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], in[1]);
    }
    return res.toArray(new int[res.size()][]);
}
1
2
3
4
5
6
7
8
9
10
11

Python：

def merge(self, intervals):
    intervals.sort(key=lambda x: x[0])
    res = [intervals[0]]
    for s, e in intervals[1:]:
        if s > res[-1][1]: res.append([s, e])
        else: res[-1][1] = max(res[-1][1], e)
    return res
1
2
3
4
5
6
7

C++：

vector<vector<int>> merge(vector<vector<int>>& ins) {
    sort(ins.begin(),ins.end());
    vector<vector<int>> res;
    for(auto& in:ins){ if(res.empty()||res.back()[1]<in[0]) res.push_back(in); else res.back()[1]=max(res.back()[1],in[1]); }
    return res;
}
1
2
3
4
5
6

复杂度：O(NlogN)/O(N)。

相关：152 无重叠区间

# 加油站（Gas Station）

LeetCode 134 · ⭐⭐ · 贪心

# 01. 题目

环形路线，gas[i] 加油量，cost[i] 消耗量。找能绕一圈的起点。

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

# 02. 题目分析

flowchart TD
    A["遍历0..n-1"] --> B["diff = gas[i]-cost[i]"]
    B --> C["total += diff, tank += diff"]
    C --> D{"tank < 0 ?"}
    D -->|YES| E["start=i+1, tank=0(重新开始)"]
    D -->|NO| F["继续"]
    E & F --> G{"遍历完?"}
    G -->|YES| H{"total >= 0 ?"}
    H -->|YES| I["返回start"]
    H -->|NO| J["-1(不可达)"]
1
2
3
4
5
6
7
8
9
10

核心：若从 A 出发到不了 B，则 A~B 之间任一点出发也到不了 B。所以直接跳过这段。

# 03. 代码

Java：

public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff; tank += diff;
        if (tank < 0) { start = i + 1; tank = 0; }
    }
    return total >= 0 ? start : -1;
}
1
2
3
4
5
6
7
8
9

Python：

def canCompleteCircuit(self, gas, cost):
    total = tank = start = 0
    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total += diff; tank += diff
        if tank < 0: start = i + 1; tank = 0
    return start if total >= 0 else -1
1
2
3
4
5
6
7

C++：

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total=0,tank=0,start=0;
    for(int i=0;i<gas.size();i++){ int diff=gas[i]-cost[i]; total+=diff; tank+=diff; if(tank<0){ start=i+1; tank=0; } }
    return total>=0?start:-1;
}
1
2
3
4
5

复杂度：O(N)/O(1)。

# 04. 总结

核心 说明
total 总油量差，total>=0 才有解
tank 当前段剩余油量，<0 则重置
贪心 跳过不可达的段

相关：157 摆动序列

# 摆动序列（Wiggle Subsequence）

LeetCode 376 · ⭐⭐ · 贪心 / DP

# 01. 题目

最长的交替增减子序列长度。[1,7,4,9,2,5] → 6（全部交替）。[1,17,5,10,13,15,10,5,16,8] → 7。

# 02. 题目分析

flowchart TD
    A["up=1, down=1"] --> B["i=1..n-1"]
    B --> C{"nums[i] > nums[i-1] ?"}
    C -->|YES| D["up = down + 1(上升接下降)"]
    C -->|NO| F{"nums[i] < nums[i-1] ?"}
    F -->|YES| G["down = up + 1(下降接上升)"]
    D & G & F --> B
1
2
3
4
5
6
7

核心：up 以上升结尾的最长摆动，down 以下降结尾的最长摆动。

nums=[1,7,4,9,2,5]
i=1: 7>1 → up=down+1=2
i=2: 4<7 → down=up+1=3
i=3: 9>4 → up=down+1=4
i=4: 2<9 → down=up+1=5
i=5: 5>2 → up=down+1=6
→ max(up,down)=6
1
2
3
4
5
6
7

# 03. 代码

Java：

public int wiggleMaxLength(int[] nums) {
    if (nums.length < 2) return nums.length;
    int up = 1, down = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) up = down + 1;
        else if (nums[i] < nums[i - 1]) down = up + 1;
    }
    return Math.max(up, down);
}
1
2
3
4
5
6
7
8
9

Python：

def wiggleMaxLength(self, nums):
    up = down = 1
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]: up = down + 1
        elif nums[i] < nums[i-1]: down = up + 1
    return max(up, down)
1
2
3
4
5
6

C++：

int wiggleMaxLength(vector<int>& nums) {
    int up=1,down=1;
    for(int i=1;i<nums.size();i++){ if(nums[i]>nums[i-1]) up=down+1; else if(nums[i]<nums[i-1]) down=up+1; }
    return max(up,down);
}
1
2
3
4
5

复杂度：O(N)/O(1)。

# 04. 总结

核心 说明
双状态DP up 和 down 交替更新
贪心 相邻相等不更新（忽略平台）
空间优化 O(N)→O(1)

相关：149 跳跃游戏

#算法
上次更新: 2026/06/17, 12:46:05
分治算法题合集
回溯算法题合集

← 回溯算法题合集→

最近更新
01
信号崩溃快速排查
06-15
02
CoreDump破案
06-15
03
perf火焰图实战
06-15
更多文章>
Theme by Vdoing | Copyright © 2019-2026 杨充 | MIT License | 桂ICP备2024034950号 | 桂公网安备45142202000030