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

贪心章节的题目，做不出来看题解的时候，千万别有 “为什么这都没想到” 的感觉，想不出来是正常的，转变心态 “妙啊，又学到了新的思路” ，这样能避免消极的心态对做题效率的影响。

134. 加油站

按卡哥的思路：

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

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

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

这种其实算是暴力解法的优化，相当于利用了前面的信息，当 sum 变成负数时，确认了 [ 0 ，i ] 的点都无法作为起点。

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

如果出现更大的负数，就是更新i，那么起始位置又变成新的i+1了。那有没有可能 [0，i] 区间 选某一个作为起点，累加到 i这里 curSum是不会小于零？

证明采用反证法，用卡哥的图来解释

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

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

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {   // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};

本题困扰我很久的地方在于另一种解法，我最开始将 gas[i] - cost[i] 的值做成数组，再利用前缀和的技巧，直观地想到，前缀和最低点的后一个点是最佳起点，以它为起点的后半段一定是能走通的，再保证全程有盈余，就可以走完全程。亏空最严重的一个点必须放在最后一步走，等着前面剩余的救助。

这种思路的想法是比较直觉的，问题在于这个加油站是环形的，怎么证明从不同的起点出发，无论能不能走完全程，全局最低点的位置是不变的。

这个结论的前提条件有点多，但题目都满足：

1、环形的数组。

2、起点可以变化，但数组中的元素及其顺序是固定的。换句话说，我们在分析累积和时并没有改变任何元素的值，只是改变了它们被累加的起始点和顺序。

3、数组的总和要大于0，即题目要求的有解，且必须是唯一解，多解的话这个解法失效，需要添加额外的判定条件。

4、环形数组中的元素是连续分布的，并且在整个分析过程中保持不变。

5、累积和计算方法是线性的，即从选定的起点开始，依次加上下一个元素，直到数组结束，然后继续从数组的开始处累加，直到返回到起点之前的元素。

满足这些条件才能保证，接下来详细说明。

如下图所示，从 0 索引开始的 curSum 的值的变化可以用折线图表示。

满足上述前提的话，在改变起点位置时，如以下标 1 作为起点，我们重新绘制这个折线图，我们能发现，这个图的变化规律—— 起点从 0 变为 1，则将 1 之前的折线拼接到这个图的最右端，这个变化的原因是因为数组是环形的，并且每个位置的值没有改变，所以值的相对大小关系没有改变，只是访问的顺序改变了，导致了折线图的变化。

同时，我们还能发现折线图除了刚刚的把起点左边的折线接在了之前的末尾，折线图也在上下的平移，因为累计值变化了，但除了拼接外，图形的大体形状是没有变化的。

然后我们接着改变起点，我们能发现还是这个变化规律，同时，无论从哪个起点开始，折线图的最低点永远是不变的。

在环形结构中，最低点的不变性基于一个事实：所有可能的前缀和最低值是从数组中某个特定序列的累积得到的，这个序列不会因为起点的改变而改变其累积和的值。虽然累积和的起点改变了，但你依然是在处理同样的一组数值，只是顺序变了。因此，数组中存在的最小和最大累积和出现的位置不会因为起点的改变而改变，它们只是在计算过程中出现的时间变了。每次你重新开始累积时，你都是在重新排列这些相同的值。最低点是由这些值的固定组合决定的，而不是由起点决定的。

这是通过观察折线图得出的结论，并不是严谨的数学证明。

解释完这个结论后，通过折线图来解释这个过程的话，我们在做的就是寻找在遍历所有点时， curSum 都不会小于0，如果存在这样的折线图，那么就找到了唯一解。

public int canCompleteCircuit(int[] gas, int[] cost) {
    int len = gas.length;
    int spare = 0;
    int minSpare = Integer.MAX_VALUE;
    int minIndex = 0;

    for (int i = 0; i < len; i++) {
        spare += gas[i] - cost[i];
        if (spare < minSpare) {
            minSpare = spare;
            minIndex = i;
        }
    }

    return spare < 0 ? -1 : (minIndex + 1) % len;
}

这两种思路其实代码都是差不多的，几乎没有不同，只是从两个角度得出的相同的结论。

135. 分发糖果

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 从前向后
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
        }
        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] ) {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        // 统计结果
        int result = 0;
        for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
        return result;
    }
};

这题学习到了前后两次遍历的解法。

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

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

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

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

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

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