K次取反后最大化的数组
1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
本题首先想到尽可能将负的数变成正数，这样才能得到最大和,将数组进行按绝对值大小进行降序排序，若遇到负数将其取反后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--if (nums[i] < 0 && K > 0) {nums[i] = -nums[i];K--;}}// 如果K还大于0，那么反复转变数值最小的元素，将K用完if (K % 2 == 1)nums[len - 1] = -nums[len - 1];return Arrays.stream(nums).sum();}
}加油站
134. 加油站 - 力扣（LeetCode）
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
如图：
那么为什么一旦[0，i] 区间和为负数，起始位置就可以是i+1呢，i+1后面就不会出现更大的负数？
如果出现更大的负数，就是更新i，那么起始位置又变成新的i+1了。
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int cursum = 0;int totalsum = 0;int startIndex = 0;for (int i = 0; i < gas.length; i++) {cursum += gas[i] - cost[i];totalsum += gas[i] - cost[i];if (cursum < 0) {startIndex = (i + 1) % gas.length;cursum = 0;}}if (totalsum < 0) {return -1;}return startIndex;}
}分发糖果
135. 分发糖果 - 力扣（LeetCode）
按照先处理一边，在处理一边的思路进行模拟
先确定右边评分大于左边的情况（也就是从前向后遍历）
此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
局部最优可以推出全局最优。
如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1
再确定左孩子大于右孩子的情况（从后向前遍历）
遍历顺序这里有同学可能会有疑问，为什么不能从前向后遍历呢？
因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果，所以 要从后向前遍历。
代码：
class Solution {public int candy(int[] ratings) {int[] Candy = new int[ratings.length];Arrays.fill(Candy, 1);for (int i = 1; i < ratings.length; i++) {//右边比左边大的情况if (ratings[i] > ratings[i - 1]) {Candy[i] = Candy[i - 1] + 1;}}for (int i = ratings.length - 2; i >= 0; i--) {//左边比右边大的情况，注意从后向前遍历if (ratings[i] > ratings[i + 1]) {Candy[i] = Math.max(Candy[i], Candy[i + 1] + 1);//取最大值}}return Arrays.stream(Candy).sum();}
}
)
)
