应用场景
所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
饼干分孩子问题
public static int getCookies(int[] children, int[] cookies) {
// 将饼干和饥饿度进行排序
Arrays.sort(children);
Arrays.sort(cookies);
// 初始设置饼干的指针和已经吃饱的人数
int i = 0;
int j = 0;
// 按照从小到大的饼干依次尝试能否吃饱饥饿度最低的孩子
while (i < cookies.length && j < children.length) {
// 如果当前孩子能够吃饱，则将饼干的指针后移一位
if (cookies[i++] >= children[j]) {
j++;
}
}
return j;
}
去除交叉区间
public static int[][] removeCrossRange(int[][] ranges) {
// 先将区间列表按每个区间最大值进行排序
Arrays.sort(ranges, Comparator.comparingInt(o -> o[1]));
// 初始化列表，添加首个区间
List<int[]> newRanges = new ArrayList<>();
newRanges.add(ranges[0]);
// 设置首个区间的最大值为参考值
int ref = ranges[0][1];
// 遍历第二个区间往后的所以区间
for (int i = 1; i < ranges.length; i++) {
// 如果当前区间的最小值大于参考值，则说明两个区间没有重复
if (ranges[i][0] > ref) {
newRanges.add(ranges[i]);
// 将参考的区间的最大值提升到替换后的值
ref = ranges[i][1];
}
}
return newRanges.toArray(new int[0][]);
}
股票最佳收益
public static int bestStockProfits(int[] stocks) {
int profits = 0;
for (int i = 0; i < stocks.length - 1; i++) {
if (stocks[i + 1] > stocks[i]) {
profits += stocks[i + 1] - stocks[i];
}
}
return profits;
}
