面试 TOP101 贪心专题题解汇总Java版（BM95 —— BM96）
贪心算法
| 题号 | 题目名称 | 核心思路 | 时间复杂度 | 空间复杂度 | 代码亮点 | 牛客原题链接 |
|---|---|---|---|---|---|---|
| BM95 | 分糖果问题 | 两次贪心扫描：先左→右，再右→左 | O(n) | O(n) | 无需回溯，两次线性遍历即可满足相邻与高分的双重约束 | 🔗 直达 |
| BM96 | 主持人调度（二） | 贪心 + 双指针（或最小堆） | O(n log n) | O(n) | 将起止时间拆开排序，扫描线思想；堆写法更直观 | 🔗 直达 |
✅ 复习顺序建议（由易到难）
BM95 → BM96
BM95 分糖果问题
分糖果问题_牛客题霸_牛客网
https://www.nowcoder.com/practice/76039109dd0b47e994c08d8319faa352?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
import java.util.*;public class Solution {public int candy(int[] arr) {int n = arr.length; // 1. 获取孩子数量if (n <= 1) return n; // 2. 只有一个孩子直接返回 1int[] ans = new int[n]; // 3. 每个孩子糖果数Arrays.fill(ans, 1); // 4. 初始每人 1 颗// 5. 从左到右：右邻居高则多给 1for (int i = 1; i < n; i++) {if (arr[i] > arr[i - 1]) ans[i] = ans[i - 1] + 1;}// 6. 从右到左：左邻居高且糖果不足则补for (int i = n - 2; i >= 0; i--) {if (arr[i] > arr[i + 1] && ans[i] <= ans[i + 1])ans[i] = ans[i + 1] + 1;}return Arrays.stream(ans).sum(); // 7. 返回糖果总数}
}
BM96 主持人调度（二）
主持人调度（二）_牛客题霸_牛客网
https://www.nowcoder.com/practice/4edf6e6d01554870a12f218c94e8a299?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
- 分开排序 + 计算区间的个数
import java.util.*;public class Solution {public int minmumNumberOfHost(int n, int[][] startEnd) {int[] st = new int[n]; // 1. 存储所有会议开始时间int[] ed = new int[n]; // 2. 存储所有会议结束时间for (int i = 0; i < n; i++) { // 3. 拆分输入数组到 st[] 和 ed[]st[i] = startEnd[i][0];ed[i] = startEnd[i][1];}Arrays.sort(st); // 4. 升序排序开始时间Arrays.sort(ed); // 5. 升序排序结束时间int res = 0; // 6. 所需最少主持人数量int j = 0; // 7. 指向最早结束的会议for (int i = 0; i < n; i++) { // 8. 遍历所有开始时间if (st[i] >= ed[j]) { // 9. 当前会议开始前已有会议结束，主持人可复用j++; // 10. 释放该主持人} else { // 11. 无空闲主持人，需新增res++;}}return res; // 12. 返回结果}
}
- 重载排序+大顶堆
import java.util.*;public class Solution {public int minmumNumberOfHost (int n, int[][] startEnd) {Arrays.sort(startEnd, new Comparator<int[]>() { // 1. 按会议开始时间升序排序public int compare(int[] o1, int[] o2) { // 2. 自定义比较器return Integer.compare(o1[0], o2[0]); // 3. 比较会议的开始时间}});PriorityQueue<Integer> pq = new PriorityQueue<>(); // 4. 创建小顶堆，记录各会议室的最早释放时间pq.offer(Integer.MIN_VALUE); // 5. 先放入哨兵值，避免首次 poll 时空指针for (int i = 0; i < n; i++) { // 6. 遍历每场会议if (pq.peek() <= startEnd[i][0]) { // 7. 最早结束的会议室已空闲，复用该主持人pq.poll(); // 8. 弹出该释放时间}pq.offer(startEnd[i][1]); // 9. 把当前会议的结束时间压入堆}return pq.size(); // 10. 堆大小即为所需最少主持人数量}
}