應(yīng)用場(chǎng)景
所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇巍实，即貪心選擇來達(dá)到筒狠。
餅干分孩子問題
public static int getCookies(int[] children, int[] cookies) {
// 將餅干和饑餓度進(jìn)行排序
Arrays.sort(children);
Arrays.sort(cookies);
// 初始設(shè)置餅干的指針和已經(jīng)吃飽的人數(shù)
int i = 0;
int j = 0;
// 按照從小到大的餅干依次嘗試能否吃飽饑餓度最低的孩子
while (i < cookies.length && j < children.length) {
// 如果當(dāng)前孩子能夠吃飽，則將餅干的指針后移一位
if (cookies[i++] >= children[j]) {
j++;
}
}
return j;
}
去除交叉區(qū)間
public static int[][] removeCrossRange(int[][] ranges) {
// 先將區(qū)間列表按每個(gè)區(qū)間最大值進(jìn)行排序
Arrays.sort(ranges, Comparator.comparingInt(o -> o[1]));
// 初始化列表，添加首個(gè)區(qū)間
List<int[]> newRanges = new ArrayList<>();
newRanges.add(ranges[0]);
// 設(shè)置首個(gè)區(qū)間的最大值為參考值
int ref = ranges[0][1];
// 遍歷第二個(gè)區(qū)間往后的所以區(qū)間
for (int i = 1; i < ranges.length; i++) {
// 如果當(dāng)前區(qū)間的最小值大于參考值谅年，則說明兩個(gè)區(qū)間沒有重復(fù)
if (ranges[i][0] > ref) {
newRanges.add(ranges[i]);
// 將參考的區(qū)間的最大值提升到替換后的值
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;
}
