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

思路：

先排序，在循环条件while(k>0 && i<nums.size() && nums[i]<0)下，nums[i]=(-1)*nums[i]，然后k--,i++.

再排序，如果k依旧大于0，如果k是奇数，则将最小的数变成负数。最后sum加和所有元素。return sum ;

看视频后：

本题包含了两次贪心：

1. 找绝对值最大的负数进行取反

2. k没用完 且 都为正数的情况 找最小值进行k次取反

按绝对值排只需要排序一次。

134. 加油站

思路：

用数组存储差值，根据极点判断极点加1是否为start，但部分用例过不去

看视频后：

用currentSum和totalSum

totalSum用来最后判断是否为-1；

currentSum用来寻找start节点，如果currentSum<0则意味着在这之前及该节点都不可能为start节点，start更新为i+1;

for(int i=0;i<minor.size();i++)

        {

            totalSum+=minor[i];

            currentSum+=minor[i];

            if(currentSum<0)

            {

                start=i+1;

                currentSum=0;

            }

        }

135. 分发糖果

思路：

先小于判断，后大于判断，但数值不对。

看视频后：

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

先确定右边大于左边的情况：（从前向后）

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

for(int i=1;i<ratings.size();i++)

        {

            if(ratings[i]>ratings[i-1])

                candies[i]=candies[i-1]+1;

        }

然后确定左边大于右边的情况：(从后往前）

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

获得左边大于右边的最优。

此时注意新的贪心：局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。即取最大值。

for(int i=ratings.size()-2;i>=0;i--)

        {

            if(ratings[i]>ratings[i+1])

                candies[i]=max(candies[i],candies[i+1]+1);

        }

最后对candies进行加和。