贪心算法基础

应用场景

所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

饼干分孩子问题

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;
    }