【贪心算法】代码随想录算法训练营第三十三天 |1005.K次取反后最大化的数组和，134.加油站，135.分发糖果（待补充）

「爱情、让人受尽委屈。」 2024-04-23 04:18 44阅读 0赞

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

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A\[i\] 替换为 -A\[i\]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）

以这种方式修改数组后，返回数组可能的最大和。

示例 1：

*  输入：A = \[4,2,3\], K = 1
 *  输出：5
 *  解释：选择索引 (1,) ，然后 A 变为 \[4,-2,3\]。

示例 2：

*  输入：A = \[3,-1,0,2\], K = 3
 *  输出：6
 *  解释：选择索引 (1, 2, 2) ，然后 A 变为 \[3,1,0,2\]。

示例 3：

*  输入：A = \[2,-3,-1,5,-4\], K = 2
 *  输出：13
 *  解释：选择索引 (1, 4) ，然后 A 变为 \[2,3,-1,5,4\]。

提示：

*  1 <= A.length <= 10000
 *  1 <= K <= 10000
 *  \-100 <= A\[i\] <= 100

4、视频讲解：

[贪心算法，这不就是常识？还能叫贪心？LeetCode：1005.K次取反后最大化的数组和\_哔哩哔哩\_bilibili][LeetCode_1005.K_bilibili]

5、思路：

本题思路其实比较好想了，如何可以让数组和最大呢？

贪心的思路，局部最优：**让绝对值大的负数变为正数，当前数值达到最大**，整体最优：整个数组和达到最大。

局部最优可以推出全局最优。

那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。

那么又是一个贪心：局部最优：**只找数值最小的正整数进行反转，当前数值和可以达到最大**（例如正整数数组\{5, 3, 1\}，反转1 得到-1 比 反转5得到的-5 大多了），全局最优：整个 数组和 达到最大。

虽然这道题目大家做的时候，可能都不会去想什么贪心算法，一鼓作气，就AC了。

**我这里其实是为了给大家展现出来 经常被大家忽略的贪心思路，这么一道简单题，就用了两次贪心！**

那么本题的解题步骤为：

*  第一步：将数组按照绝对值大小从大到小排序，**注意要按照绝对值的大小**
 *  第二步：从前向后遍历，遇到负数将其变为正数，同时K--
 *  第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
 *  第四步：求和

### 总结 ###

贪心的题目如果简单起来，会让人简单到开始怀疑：本来不就应该这么做么？这也算是算法？我认为这不是贪心？

本题其实很简单，不会贪心算法的同学都可以做出来，但是我还是全程用贪心的思路来讲解。

因为贪心的思考方式一定要有！

**如果没有贪心的思考方式（局部最优，全局最优），很容易陷入贪心简单题凭感觉做，贪心难题直接不会做，其实这样就锻炼不了贪心的思考方式了**。

所以明知道是贪心简单题，也要靠贪心的思考方式来解题，这样对培养解题感觉很有帮助。

class Solution {
        public int largestSumAfterKNegations(int[] nums, int k) {
            // 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
            nums = IntStream.of(nums)
                    .boxed()
                    .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                    .mapToInt(Integer::intValue).toArray();
            int len = nums.length;
            for (int i = 0; i < len; i++) {
                // 从前向后遍历，遇到负数并且k大于0，则将其变为正数，同时k--
                if (nums[i] < 0 && k > 0) {
                    nums[i] = -nums[i];
                    k--;
                }
            }
            // 如果k还大于0，则将最后一个元素取反
            if (k % 2 == 1) {
                nums[len - 1] = -nums[len - 1];
            }
            return Arrays.stream(nums).sum();
        }
    }

## 134.加油站 ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas\[i\] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost\[i\] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

*  如果题目有解，该答案即为唯一答案。
 *  输入数组均为非空数组，且长度相同。
 *  输入数组中的元素均为非负数。

示例 1: 输入:

*  gas = \[1,2,3,4,5\]
 *  cost = \[3,4,5,1,2\]

输出: 3 解释:

*  从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
 *  开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
 *  开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
 *  开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
 *  开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
 *  开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
 *  因此，3 可为起始索引。

示例 2: 输入:

*  gas = \[2,3,4\]
 *  cost = \[3,4,3\]
 *  输出: -1
 *  解释: 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油。开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油。开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油。你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。因此，无论怎样，你都不可能绕环路行驶一周。

4、视频链接：

[贪心算法，得这么加油才能跑完全程！LeetCode ：134.加油站\_哔哩哔哩\_bilibili][LeetCode _134._bilibili]

5、思路：

可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest\[i\]相加一定是大于等于零的。

每个加油站的剩余量rest\[i\]为gas\[i\] - cost\[i\]。

i从0开始累加rest\[i\]，和记为curSum，一旦curSum小于零，说明\[0, i\]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

如图：

![e32191952f78c113cb6cf1a4715370e1.png][]

那么为什么一旦\[0，i\] 区间和为负数，起始位置就可以是i+1呢，i+1后面就不会出现更大的负数？

如果出现更大的负数，就是更新i，那么起始位置又变成新的i+1了。

那有没有可能 \[0，i\] 区间 选某一个作为起点，累加到 i这里 curSum是不会小于零呢？ 如图：

![fe559afe67f97871059c3c38413745fd.png][]

如果 curSum<0 说明 区间和1 + 区间和2 < 0， 那么 假设从上图中的位置开始计数curSum不会小于0的话，就是 区间和2>0。

区间和1 + 区间和2 < 0 同时 区间和2>0，只能说明区间和1 < 0， 那么就会从假设的箭头初就开始从新选择其实位置了。

**那么局部最优：当前累加rest\[i\]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置**。

局部最优可以推出全局最优，找不出反例，试试贪心！

class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int curSum = 0;
            int totalSum = 0;
            int index = 0;
            for (int i = 0; i < gas.length; i++) {
                curSum += gas[i] - cost[i];
                totalSum += gas[i] - cost[i];
                if (curSum < 0) {
                    index = (i + 1) % gas.length;
                    curSum = 0;
                }
            }
            if (totalSum < 0) return -1;
            return index;
        }
    }

## 135.分发糖果 ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 3]

3、题目：

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

*  每个孩子至少分配到 1 个糖果。
 *  相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

*  输入: \[1,0,2\]
 *  输出: 5
 *  解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

*  输入: \[1,2,2\]
 *  输出: 4
 *  解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

4、视频链接：

[贪心算法，两者兼顾很容易顾此失彼！LeetCode：135.分发糖果\_哔哩哔哩\_bilibili][LeetCode_135._bilibili]

5、思路：

这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，**如果两边一起考虑一定会顾此失彼**。

先确定右边评分大于左边的情况（也就是从前向后遍历）

此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果

局部最优可以推出全局最优。

如果ratings\[i\] > ratings\[i - 1\] 那么\[i\]的糖 一定要比\[i - 1\]的糖多一个，所以贪心：candyVec\[i\] = candyVec\[i - 1\] + 1

如图：

![f11f2105df35ae288daaa60a21c71c0a.png][]

再确定左孩子大于右孩子的情况（从后向前遍历）

遍历顺序这里有同学可能会有疑问，为什么不能从前向后遍历呢？

因为 rating\[5\]与rating\[4\]的比较 要利用上 rating\[5\]与rating\[6\]的比较结果，所以 要从后向前遍历。

如果从前向后遍历，rating\[5\]与rating\[4\]的比较 就不能用上 rating\[5\]与rating\[6\]的比较结果了 。如图：

![f3e719ebd04a6ea7a97a1219fe9f8e6f.png][]

**所以确定左孩子大于右孩子的情况一定要从后向前遍历！**

如果 ratings\[i\] > ratings\[i + 1\]，此时candyVec\[i\]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec\[i + 1\] + 1（从右边这个加1得到的糖果数量），一个是candyVec\[i\]（之前比较右孩子大于左孩子得到的糖果数量）。

那么又要贪心了，局部最优：取candyVec\[i + 1\] + 1 和 candyVec\[i\] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

局部最优可以推出全局最优。

所以就取candyVec\[i + 1\] + 1 和 candyVec\[i\] 最大的糖果数量，**candyVec\[i\]只有取最大的才能既保持对左边candyVec\[i - 1\]的糖果多，也比右边candyVec\[i + 1\]的糖果多**。

如图：

![ca37ef9eb022b2cf626f5a6febf3b51f.png][]

所以该过程代码如下：

// 从后向前
    for (int i = ratings.size() - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1] ) {
            candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
        }
    }

### 总结 ###

这在leetcode上是一道困难的题目，其难点就在于贪心的策略，如果在考虑局部的时候想两边兼顾，就会顾此失彼。

那么本题我采用了两次贪心的策略：

*  一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
 *  一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。

class Solution {
        /**
         * 分两个阶段
         * 1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
         * 2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
         */
        public int candy(int[] ratings) {
            int len = ratings.length;
            int[] candyVec = new int[len];
            candyVec[0] = 1;
            // 1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
            for (int i = 1; i < len; i++) {
                candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
            }
    //         2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，
    //         此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
            for (int i = len - 2; i >= 0; i--) {
                if (ratings[i] > ratings[i + 1]) {
                    candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
                }
            }
    
            int ans = 0;
            for (int num : candyVec) {
                ans += num;
            }
            return ans;
        }
    }

[LeetCode_ -]: https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
[Link 1]: https://www.programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html
[LeetCode_1005.K_bilibili]: https://www.bilibili.com/video/BV138411G7LY
[LeetCode_ - 1]: https://leetcode.cn/problems/gas-station/
[Link 2]: https://www.programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode _134._bilibili]: https://www.bilibili.com/video/BV1jA411r7WX
[e32191952f78c113cb6cf1a4715370e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/b25da611ce0e4644b848eebd78af39d8.png
[fe559afe67f97871059c3c38413745fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/7399491f1d994d2b82ad7109f0dcbd65.png
[LeetCode_ - 2]: https://leetcode.cn/problems/candy/
[Link 3]: https://www.programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_135._bilibili]: https://www.bilibili.com/video/BV1ev4y1r7wN
[f11f2105df35ae288daaa60a21c71c0a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/f26e1f39bb05437fab9c03b2e4fb55b2.png
[f3e719ebd04a6ea7a97a1219fe9f8e6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/3c86ce95614841e68cf8eff9d5a9d36b.png
[ca37ef9eb022b2cf626f5a6febf3b51f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5615a2bf8203416d8feb4809abe9afa4.png