贪心算法

怎样理解贪心

贪心的本质是选择每一个阶段的局部最优，从而达到全局最优的目标。也就是在每个问题的决策阶段，都选择当前看起来最优的选择（贪心）。
究竟什么时候用到贪心？

• 能通过局部最优推出整体最优，就可以尝试贪心策略；若不可行，可能需要动态规划

贪心算法的一般解题步骤：

• 将大问题分解为若干子问题
• 总结出合适的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

贪心算法和动态规划的区别：

• 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解
• 贪心算法不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决

零钱兑换问题

给定 n 种硬币，第 i 种硬币的面值为 coins[i-1]，目标金额为 amt，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。若无法凑出目标金额则返回 -1。

• 每次选择不大于且最接近它的硬币，不断循环该步骤，直到凑出目标金额

public int coinChangeGreedy(int[] coins, int amt){
    //coins数组有序
    int i = coins.length - 1;
    int count = 0;
    //amt表示还需要凑的金额
    while(amt > 0){
        //如果当前要拿的硬币面额，大于要凑的金额，就拿小的去吧！
        while(i > 0 && coins[i] > amt){
            i--;
        }
        amt -= coins[i];
        count++;
    }
    return amt == 0 ? count : -1;
}

贪心策略的局限性：

• 对于某些硬币面值组合，贪心算法并不能找到最优解，例如 [1, 20, 50]，为了凑总金额为 60 元，贪心算法会选择拿一枚 50 元硬币，以及 10 枚 1 元硬币，而并非 3 枚 20 元硬币

也就是说，对于零钱兑换问题，贪心算法无法保证找到全局最优解，并且甚至会找到非常差的解，该问题更适合用动态规划解决。
一般来说，贪心算法的适用情况分为以下两种：

• 可以保证找到全局最优解：贪心算法在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效
• 可以找到近似最优解：贪心算法在这种情况下也是可用的。对于很多复杂问题来说，寻找全局最优解非常困难，能以较高效率找到次优解也是非常不错的

分数背包问题

给定 n 个物品，第 i 个物品的重量为 wgt[i-1]，价值为 val[i-1]，和一个容量为 cap 的背包，每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，问在限定背包容量下背包中物品的最大价值。

• 和0-1背包的不同点在于，分数背包允许选择物品的一部分，由此我们可以对物品进行任意切分，并按照重量比例来计算相应价值
• 对于物品 i，它在单位重量下的价值为 val[i-1] / wgt[i-1]；假设放入部分物品 i，重量为 w，则背包增加的总价值为 w * val[i-1] / wgt[i-1]
• 由于背包可以装的总重量是一定的，所以为了保证总价值最大，必须使得单位重量下价值保证最高，因此本题贪心策略的本质是最大化单位重量下的物品价值
• 将所有物品按照单位价值从高到低进行排序
• 遍历所有物品，每轮贪心地选择单位价值最高的物品
• 若剩余背包容量不足，则使用当前物品的一部分填满背包

import java.util.Arrays;
import java.util.Comparator;
// 定义物品类，包含物品的重量、价值和单位重量价值
class Item {
    int weight;
    int value;
    double ratio;
    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
        this.ratio = (double) value / weight;
    }
}
public class FractionalKnapsack {
    public static double fractionalKnapsack(int capacity, Item[] items) {
        // 按照单位重量价值从高到低对物品进行排序
        Arrays.sort(items, Comparator.comparingDouble(item -> -item.ratio));
        double totalValue = 0;
        int currentCapacity = capacity;
        // 遍历排序后的物品数组
        for (Item item : items) {
            if (currentCapacity == 0) {
                break;
            }
            if (item.weight <= currentCapacity) {
                // 如果物品的重量小于等于背包的剩余容量，则将整个物品放入背包
                totalValue += item.value;
                currentCapacity -= item.weight;
            } else {
                // 如果物品的重量大于背包的剩余容量，则取物品的一部分放入背包
                totalValue += currentCapacity * item.ratio;
                currentCapacity = 0;
            }
        }
        return totalValue;
    }
}

最大容量问题

输入一个数组 ht，其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。容器的容量等于高度和宽度的乘积（面积），其中高度由较短的隔板决定，宽度是两个隔板的数组索引之差。请在数组中选择两个隔板，使得组成的容器的容量最大，返回最大容量。

• 初始化两个指针，分别位于两端，每轮向内收缩短板指针，直到两个指针相遇
• 容器的容量是由短板决定的，如果向内收缩长板，则容器高度不变（甚至更小），宽度变小，容量是一定变小的；只有收缩短板，才有可能增加容量
• 之所以贪心比穷举更快，是因为每轮的贪心都会选择跳过一些状态，并且这些被跳过的状态都不会是最优解

int maxCapacity(int[] ht){
    int i = 0, j = ht.length - 1;
    int res = 0;
    while(i < j){
        int cap = Math.min(ht[i], ht[j]) * (j-i);
        res = Math.max(res,cap);
        if(ht[j] < ht[i]){
            i++;
        }else{
            j--;
        }
    }
    return res;
}

最大切分乘积问题

给定一个正整数 n，将其切分为至少两个正整数的和，求其切分后所有整数的乘积最大是多少。

• 3 是最好的数字！
• 除了包含 1 以及两个数都为2的情况，任何正整数对都满足：乘积大于加和，因此需要尽可能多乘（即尽可能往小分，例如 5，分成 2 和 3 一定是好的）
• 因为 3 × 3 > 2 × 2 × 2，所以尽量多用 3 进行拆分，少用 2 进行拆分，不用 1 进行拆分（1 对乘积增大毫无贡献）

public class IntegerBreakGreedy {
    public static int integerBreak(int n) {
        // 当 n 为 2 时，只能拆分为 1 + 1，乘积为 1
        if (n == 2) {
            return 1;
        }
        // 当 n 为 3 时，拆分为 1 + 2，乘积为 2
        if (n == 3) {
            return 2;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            // 如果 n 能被 3 整除，全部分解为 3
            return (int) Math.pow(3, quotient);
        } else if (remainder == 1) {
            // 如果余数为 1，把一个 3 和 1 组合成 4，即 2 + 2
            return (int) Math.pow(3, quotient - 1) * 4;
        } else {
            // 如果余数为 2，直接乘上 2
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

分发饼干

力扣题目链接
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

• 大饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就先满足胃口大的孩子，不要“高射炮打蚊子”

public int assignCookies(int[] g,int[] s){
    Arrays.sort(g);
    Arrays.sort(s);
    int points = s.length - 1;
    int count = 0;
    for(int i = g.length-1; i >= 0; i--){
        if(points >= 0 && g[i] <= s[points]){
            points--;
            count++;
        }
    }
    return count;
}

摆动序列

力扣题目链接
[1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

• 这题就不用贪心了吧，其实就是前后差值正负交替一次计数一次就可以，贪心反而难理解

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null) {
            return 0;
        }
        if (nums.length < 2) {
            return nums.length;
        }
        int sum = 1;
        //先定义为null是为了确定开始时候的方向
        Boolean direction = null;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            //差值为正数，若direction为true说明上一次也是正数，则不进行sum++
            if (nums[i] - nums[i - 1] > 0) {
                if (direction != null && direction) {
                    continue;
                }
                direction = true;
            } else {
                if (direction != null && !direction) {
                    continue;
                }
                direction = false;
            }
            sum++;
        }
        return sum;
    }
}

最大子序和

力扣题目链接
给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组至少包含一个元素），返回其最大和。

• 当连续和为负数时，立刻放弃，因为如果让它加上下一个数字，还不如下一个数字自己构成的连续和

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;//用于记录最大和
        int sum = 0;//当前和
        if (nums.length == 1) {
            return nums[0];
        }
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            //更新最大连续和
            if (sum > ans) {
                ans = sum;
            }
            //加着加着变成负数了，丢弃当前和，重新开始加
            if (sum <= 0) {
                sum = 0;
            }
        }
        return ans;
    }
}

买卖股票的最佳时机

力扣题目链接
给定一个数组，它的第 i 个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

• 核心是“利润是可以分解的”，即如果第 0 天买入，第 3 天卖出，利润是 prices[3] - prices[0]，但更是 prices[3] - prices[2] + prices[2] - prices[1] + prices[1] - prices[0]
• 所以，只需要收集每天的利润，再将那些为正数的利润加起来就好了

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            ans += Math.max(prices[i] - prices[i - 1], 0);
        }
        return ans;
    }
}

跳跃游戏

力扣题目链接
给定一个非负数整数数组，最初位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度，请判断是否能够到达最后一个位置。

• 跳几步无所谓，只看每次能跳的最远的地方有没有覆盖到末尾

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(nums[i] + i, cover);
            if (cover >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

跳跃游戏Ⅱ

力扣题目链接
给定一个非负整数数组，最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度，目标是使用最少的跳跃次数到达数组的最后一个位置。

• 每次在可跳范围内选择可以使得跳的更远的位置

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int step = 0;//步数
        int end = 0;//边界
        int max = 0;//边界内能跳跃的最远距离
        for (int i = 0; i < nums.length - 1; i++) {
            max = Math.max(max, nums[i] + i);
            if (i == end) {
                end = max;
                step++;
            }
        }
        return step;
    }
}

K次取反后的最大化的数组和

力扣题目链接
给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i）。以这种方式修改数组后，返回数组可能的最大和。

• 优先用 K 次机会反转负数；若 K 有剩余，不得不开始反转正数了（注意考虑负数被反转后也变成了正数）；若负数有剩余，那么直接加起来就好了，反正也反转不了了
• 负数反转 2 次（偶数次）是没有意义的，不如反转成正数，剩下一次机会去反转最小的正数
• 负数反转 3 次（非 1 的奇数次）也是没有意义的，不如反转为正数一次，剩余两次机会去反转其他的负数（如果没有负数了，剩余两次机会也就不需要了）
• 所以必须去将负数依次反转，若没剩下K，则直接加起来；若剩下 K （负数没了），将数组重新排序，偶数则什么也不做，奇数则反转最小正数奇数次（也就是 1 次）

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (k > 0 && nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        Arrays.sort(nums);
        int ans = 0;
        if (k % 2 == 1) {
            nums[0] = -nums[0];
        }
        for (int i = 0; i < nums.length; i++) {
            ans += nums[i];
        }
        return ans;
    }
}

加油站

力扣题目链接
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

• 首先检查第 0 个加油站，并试图判断能否环绕一周；如果不能，就从第一个无法到达的加油站开始继续检查
• 若 x 加油站到不了 y 加油站，则从 x 和 y 之间的任意加油站出发，都不会到达 y 加油站
• 比如说 x 得先到 z 加油站，再到 y 加油站，既然 x 能到达 z 加油站，则说明在 z 加油站时仍有余量（余量 >= 0），那么说明 z 加油站出发的车，即使加上这个余量，也到达不了 y ，那么就说明单纯靠 z 加油站的油量出发，是根本不可能到达 y 的
• 总油量是否足够总消耗，即 totalGas >= totalCost。如果不满足这个条件，无论从哪个加油站出发都不可能绕环路一周，直接返回 -1
• 如果总油量足够总消耗，那么一定存在一个起始点可以绕环路一周。我们通过遍历过程中不断更新当前剩余油量 curGas 和起始点 start 来找到这个起始点
• start 到末尾的剩余油量是正数，总油量也足够总消耗，说明从末尾还能再回到 start

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0; // 总油量
        int totalCost = 0; // 总消耗
        int curGas = 0; // 当前剩余油量
        int start = 0; // 起始加油站编号
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            curGas += gas[i] - cost[i];
            // 如果当前剩余油量小于 0，说明从 start 到 i 之间的任何一个点都不能作为起始点
            if (curGas < 0) {
                curGas = 0;
                start = i + 1;
            }
        }
        // 如果总油量小于总消耗，无法绕环路行驶一周
        if (totalGas < totalCost) {
            return -1;
        }
        return start;
    }
}

分发糖果

力扣题目链接
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到 1 个糖果；相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？

• 先全给 1 个糖果，朝左边开始发，比前一个同学评分高，则应该多给一个
• 收回糖果，再全给 1 个糖果，朝右边开始发，比后一个同学评分高，则应该多给一个
• 两次发到手的糖果数目，多的那一个就是应该发的糖果数目，此时满足左侧规则也满足右侧规则

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        int[] right = new int[ratings.length];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        int count = left[ratings.length - 1];
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
            count += Math.max(left[i], right[i]);
        }
        return count;
    }
}

划分字母区间

力扣题目链接
给你一个字符串 s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s。返回一个表示每个字符串片段的长度的列表。

• 记录每个字母最后出现的下标位置
• 开始遍历，维护当前字符子串能够达到的最大位置
• 当遍历到的位置与最大位置相等时，即为符合条件的划分结果

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        int length = s.length();
        for (int i = 0; i < length; i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> list = new ArrayList<>();
        int start = 0, right = 0;
        for (int i = 0; i < length; i++) {
            right = Math.max(right, last[s.charAt(i) - 'a']);
            if (i == right) {
                list.add(right - start + 1);
                start = right + 1;
            }
        }
        return list;
    }
}