贪心问题感觉还是挺不好想的，因为每一题有每一题的策略，感觉只能尽量做过的记住了。

376 摆动序列

注意：是序列，而不是数组。

求最大摆动序列的长度，即求谷 / 峰的个数。

若走势不为一条直线。

起始count = 2，当trend的符号发生改变时，就增加count并修改trend，直到遍历完整个序列。

class Solution {public int wiggleMaxLength(int[] nums) {int n = nums.length;if (n < 2) {return n;}// 找到第一个不为0的trendint i = 1;int trend = 0;while (trend == 0 && i < n) {trend = nums[i] - nums[i - 1];i++;}// 如果遍历完序列，trend还是0，说明走势是一条直线if (trend == 0) {return 1;}// 起始的走势已知，count为2，遍历剩下的数字int count = 2;while (i < n) {if (trend * (nums[i] - nums[i - 1]) < 0) {// 小于0说明一定是遇到了谷或者峰，可以改变trend的方向，否则为平滑或者走势相同，不必处理count++;trend = nums[i] - nums[i - 1];}i++;}return count;}
}

53 最大子数组和

就算玛卡巴卡来了，这题也得是动态规划。

class Solution {public int maxSubArray(int[] nums) {// D[i] = Math.Max(nums[i], nums[i] + D[i - 1])int max = nums[0];int sum = nums[0];for (int i = 1; i < nums.length; i++) {sum = sum < 0 ? nums[i] : nums[i] + sum;max = Math.max(sum, max);}return max;}
}

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

贪心策略：概括地说，将最小的负数反转。

1. $k\ge coun{t}_{负数}$
   1. 多余可变换次数$k-count$为偶数，全部元素均可变为非负数，最大数组和$sum=\sum |num|$
   2. 多余可变换次数为奇数，将最小绝对值元素变为负数，最大数组和$sum=\sum |num|-2\times ab{s}_{min}$
2. $k<coun{t}_{负数}$，将最小的$k$个负数变为正数，由于数组元素具有范围，可使用代表$[-100,100]$的数组freq = new int[201]统计元素频率，然后顺序访问$freq$并计算最大和。

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {int n = nums.length;// 有多少个负数int count = 0;// 所有数字都变为正数后的和int sumAllPositive = 0;// 最小绝对值int minAbs = Integer.MAX_VALUE;// 计算上述三个变量for (int i = 0; i < n; i++) {if (nums[i] < 0) {count++;}int tmp = nums[i] < 0 ? -nums[i] : nums[i];sumAllPositive += tmp;minAbs = Math.min(minAbs, tmp);}// 如果操作次数大于负数个数和if (k >= count) {// 1、多余次数为偶数，全部元素可以都是正数if ((k - count) % 2 == 0) {return sumAllPositive;}// 2、多余次数为奇数，把有最小绝对值的数字变负else {return sumAllPositive - 2 * minAbs;}}// 3、操作次数小于负数个数的情况------------------------------------------------// 因为数字有范围，开一个数组作为哈希表，从而避免排序，空间复杂度$O(C)$// 统计freqint[] freq = new int[201];for (int i = 0;  i < n; i++) {freq[nums[i] + 100]++;}// 计算sumint sum = 0;for (int i = 0; i < 201; i++) {if (freq[i] == 0) {continue;}if (k <= 0) {// 如果能反转的都反转了，直接加就好了sum += (i - 100) * freq[i];}else {// 反转if (k >= freq[i]) {sum += (100 - i) * freq[i];k -= freq[i];}else {// 反转k个sum += (100 - i) * k;sum += (i - 100) * (freq[i] - k);k = 0;}}}return sum;}
}

134 加油站★

感觉这题贪心策略并不好想。

如果总油量减去总消耗量为负，说明无法绕圈（因为从任意点出发绕一圈的总油量-总消耗量都相等），否则可以。

贪心策略：记每个站点的剩余油量为$gas[i]-cost[i]$，i、start从0开始，累加每个站点的剩余油量。若在$i$处发现累加和小于0，则意味着$[0,i]$之间的所有站点都不能作为出发站点，将start移至$i+1$。

栗子：比如下表中列出每个站点的剩余油量。

	0	1	2	3	4	5	6	7	8	9
left	-1	1	2	-1	1	4	-10	4	2	-4
sum	-1	1	3	2	3	7	-3	4	6	2

过程如下：

1. 位置0不满足，start = 1
2. 遍历到位置6时发现不满足：
   • start = 1不可以。
   • 若start = 2，由于left > 0到达位置6时，sum必然仍小于0。故同理，不能从left >= 0的位置出发。
   • 若start = 3，left < 0，显然不能从此处出发。
3. 可知start必在7之后，start = 7，继续检查。

如果总剩余量大于0，存在解。i从0开始，累加rest[i]，和记为sum，一旦sum小于零，说明[0, i]区间都不能作为起始位置。

那么起始位置从i+1算起，再从0计算sum。

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int n = gas.length;int start = 0;int sum = 0;int totalSum = 0;for (int i = 0; i < n; i++) {sum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (sum < 0) {// sum清零，从i+1开始累计sum = 0;start = i + 1;}}return totalSum < 0 ? -1 : start;}
}

135 分发糖果★

真的，对贪心我属实只有一种办法，en记……

不过再做一遍应该就记得了，第一遍还是没啥思路了。

• 两趟遍历，一趟由前向后，处理右>左的情况；另一趟在上一趟基础上，由后向前，处理左>右的情况。

• 进阶TODO：如果是环形或者矩形呢？

import java.util.Arrays;class Solution {public int candy(int[] ratings) {int n = ratings.length;int[] candys = new int[n];// 先给每个小朋友分一个~Arrays.fill(candys, 1);// 看看右边小朋友的分数是否比左边小朋友多，如果是的话，比左边的小朋友多分一个// 例子，分数：1 2 3 4 5 4 3 2 1// 糖数：1 1 1 1 1 1 1 1 1 -> 1 2 3 4 5 1 1 1 1for (int i = 1; i < n; i++) {if (ratings[i] > ratings[i - 1]) {candys[i] = candys[i - 1] + 1;}}// 看看左边小朋友的分数是否比右边小朋友多，如果是的话，判断是否左边小朋友的糖比右边小朋友多一个以上，如果不是，补上糖果// 倒着来，这样糖数可以累加// 例子，分数：1 2 3 4 5 4 3 2 1// 糖数：1 2 3 4 5 1 1 1 1 -> 1 2 3 4 5 4 3 2 1for (int i = n - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candys[i] = Math.max(candys[i], candys[i + 1] + 1);}}int sum = 0;for (int i = 0; i < n; i++) {sum += candys[i];}return sum;}
}

860 柠檬水找零

模拟 + 贪心的简单题。

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

class Solution {public int money2index (int money) {if (money == 5) {return 0;}if (money == 10) {return 1;}return 2;}public boolean lemonadeChange(int[] bills) {int n = bills.length;// 使用一个长度为3的数组作为收银台int[] counter = new int[3];// 遍历每一位顾客的请求// 能够找零时先找大额钞票for (int i = 0; i < n; i++) {// 1、先拿进来这张钞票counter[money2index(bills[i])]++;// (1) 收到的是5元if (bills[i] == 5) {continue;}// (2) 10元if (bills[i] == 10) {// 如果没有5元的钞票，结束哩if (counter[0] <= 0) {return false;}counter[0]--;}// (3)20元else {int charge = 15;// 如果有10元可以找，先把10元钱找掉if (counter[1] > 0) {charge -= 10;counter[1]--;}// 如果5元钞票不足if (counter[0] < charge / 5) {return false;}// 否则找5元钞票counter[0] -= charge / 5;}}return true;}
}

406 根据身高重建队列★

【不仅做法要记一记，这题的语法也要记一记】

• 每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。按照身高h递减，人数k递增的顺序排序。
• 向空ArrayList中插入元素，people[i] = [hi, ki]插入位置ki。

这个题解动画做得非常之形象：https://leetcode.cn/problems/queue-reconstruction-by-height/solutions/486493/xian-pai-xu-zai-cha-dui-dong-hua-yan-shi-suan-fa-g/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;class Solution {public int[][] reconstructQueue(int[][] people) {// 按照h递减，k递增传递Arrays.sort(people, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {if (o1[0] != o2[0]) {// height更大的更优先return o2[0] - o1[0];}// k更小的更优先return o1[1] - o2[1];}});ArrayList<int[]> queue = new ArrayList<>();for (int i = 0; i < people.length; i++) {int[] person = people[i];// 在位置k处插入queue.add(person[1], person);}return queue.toArray(new int[people.length][]);}
}

738 单调递增的数字★

思路：

• 从右向左扫描数字，若发现当前数字比其左边一位（较高位）小
• 则把其左边一位数字减1，并将该位及其右边的所有位改成9

例子：

10 -> 09
100 -> 1(-1)9 -> 099
990 -> 989 -> 899 

语法：代表数字的字符数组转为数字Integer.parseInt(String.valueOf(chars))

class Solution {public int monotoneIncreasingDigits(int n) {// 将数字转为字符数组String s = String.valueOf(n);char[] chars = s.toCharArray();int start = chars.length;for (int i = chars.length - 1; i >= 1; i--) {// 非递增序，需要修改// 前一位数字减1，后面的所有数字变成9// 但是不必这样反复进行变为9的操作，记录一下最后一个位置，把最后一个位置的所有数字变为9即可if (chars[i - 1] > chars[i]) {chars[i - 1]--;start = i;}}for (int i = start; i < s.length(); i++) {chars[i] = '9';}// 字符数组转为数字return Integer.parseInt(String.valueOf(chars));}
}