贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
455.分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
//对2个数组排序，然后再从后往前逐个分配饼干，也就是胃口大的先被满足
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int res = 0;
if (s.length == 0 || g.length == 0)
return res;
for (int i = g.length - 1, j = s.length - 1; i >= 0; i--) {
if (j >= 0 && s[j] >= g[i]) {
res++;
j--;
}
}
return res;
}
}376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
只保留局部峰值，把上升和下降的峰值保留，中间的数字就不要统计，通过差值来比较
我的思路：用pre1和pre2两个指针保存前面2个不同的需要比较的值，这道题需要考虑出现多个相等值的情况，所有我用2个指针，只会保存不相等的2个值和当前的nums[i]作比较
这2个指针的更新需要注意，是每个nums[i]都需要判断更新，而不是满足摆动条件才更新
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length == 1)
return 1;
int res = 1;//初始化长度为1
int pre1 = nums[0];
int pre2 = nums[0];
int index = 0;
//找到pre2的位置和值
for (int i = 1; i < nums.length; i++) {
index = i;
if (nums[i] != pre1) {
pre2 = nums[i];
break;
}
}
//找到不相同的数字，那就结果已经有2个长度满足了
if (pre1 != pre2)
res = 2;
//从pre2的下一个位置开始遍历
for (int i = index + 1; i < nums.length; i++) {
//差值为一正一负，那就是相乘小于0
if ((nums[i] - pre2) * (pre2 - pre1) < 0) {
res++;
}
//这里注意，只有nums[i]!=pre2 我们才去更新pre1 pre2
//每个位置都会判断更新pre1 pre2
if (nums[i] != pre2) {
pre1 = pre2;
pre2 = nums[i];
}
}
return res;
}
}53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
- 输入: [-2,1,-3,4,-1,2,1,-5,4]
- 输出: 6
- 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution {
//思路：count不断累积元素值，如果count是负数，那就重置为0
//因为负数累加的值会更小，需要恢复为0继续相加下一个元素
public int maxSubArray(int[] nums) {
int res=nums[0];
int count=0;
for(int i=0;i<nums.length;i++){
count+=nums[i];
res=Math.max(res,count);
if(count<0){
count=0;
}
}
return res;
}
}122.买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路：只需要收集每天的正利润
class Solution {
public int maxProfit(int[] prices) {
int profit=0;
for(int i=1;i<prices.length;i++){
if(prices[i]>prices[i-1]){
profit+=prices[i]-prices[i-1];
}
}
return profit;
}
}55. 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
class Solution {
public boolean canJump(int[] nums) {
if (nums.length == 1)
return true;
int maxStep = 0;
int step = 0;
for (int i = 0; i <= maxStep; i++) {
//计算当前元素可以到达的最大位置
//这里注意，要保证当前位置是可以到达的，这个就通过i <= maxStep判断
step = i + nums[i];
//遍历过程中，计算保留最大的可以到达的位置
maxStep = Math.max(maxStep, step);
//如果最大可以到达的位置超过数组大小，那肯定是true
if (maxStep >= nums.length - 1)
return true;
}
return false;
}
}45.跳跃游戏 II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
贪心：在 i 能够跳跃到 i+j 的这个区间中，找出我们要跳跃的位置，也就是可以求出最大索引的元素，就相当于第一次跳到了这个，然后就继续循环遍历这个元素能够到达的区间，继续求最大索引，就尽量保证都是跳最远，花费的跳跃次数最少
class Solution {
public int jump(int[] nums) {
if(nums.length==1) return 0;
int maxStep=nums[0];
int count=0;
int res=0;
//for循环遍历元素最大跳跃到的位置，在这个区间中又继续求出最大的索引值
//保留作为下一次继续遍历的边界
for(int i=0;i<=maxStep;i++){
count=Math.max(count,i+nums[i]);
//结束一次maxstep的遍历时，就跳了一次 记录最大到达的位置count赋值给maxstep
//改变maxstep后又会继续遍历后面的一次跳跃
if(i==maxStep) {
res++;
maxStep=count;
}
if(maxStep>=nums.length-1) return res+1;
}
return res;
}
}1005.K次取反后最大化的数组和
给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。
思路：先把所有的负数反过来，然后遇到0就直接把k变为0
如果k还剩余，就进行排序，把最小的正整数反复变化，如果k是偶数，那变化后还是正数
如果是奇数，就需要sum减去第一个元素值。
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < 0 && k > 0) {
nums[i] = -nums[i];
k--;
}
if (nums[i] == 0)
k = 0;
sum += nums[i];
}
k = k % 2;
if (k == 1) {
Arrays.sort(nums);
sum -= 2 * nums[0];
}
return sum;
}
}134. 加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
- 如果题目有解，该答案即为唯一答案。
- 输入数组均为非空数组，且长度相同。
- 输入数组中的元素均为非负数。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int index = 0;
int sum = 0;
int count = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
// 求出所有的剩余油量，如果小于0，肯定跑不完
sum += diff;
// 记录区间内的求和，如果小于0，说明从0到i的位置都不能作为起点，
// 需要找下一个i+1 重新把count变为0
count += diff;
if (count < 0) {
index = i + 1;
count = 0;
}
}
if (sum < 0)
return -1;
return index;
}
}135. 分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
思路：采用两次贪心的策略：
- 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
- 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
class Solution {
public int candy(int[] ratings) {
if (ratings.length == 1)
return 1;
int[] candy = new int[ratings.length];
candy[0] = 1;
int count = 0;
for (int i = 1; i < ratings.length; i++) {
candy[i] = 1;
if (ratings[i] > ratings[i - 1])
candy[i] = candy[i - 1] + 1;
}
for (int i = ratings.length - 2; i >= 0; i--) {
//这里需要注意用到Math.max，因为要维持原来的值，又需要保证右边的元素
if (ratings[i] > ratings[i + 1])
candy[i] = Math.max(candy[i], candy[i + 1] + 1);
}
for (int i = 0; i < ratings.length; i++) {
count += candy[i];
}
return count;
}
}860.柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
针对20的情况，优先找零10+5 不够再5+5+5 因为5留给后面用处更多
class Solution {
public boolean lemonadeChange(int[] bills) {
int five=0;
int ten=0;
for(int i=0;i<bills.length;i++){
if(bills[i]==5) five++;
if(bills[i]==10){
if(five<=0) return false;
five--;
ten++;
}
if(bills[i]==20){
if(ten>0){
ten--;
five--;
}
else{
five-=3;
}
if(five<0||ten<0) return false;
}
}
return true;
}
}406.根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
class Solution {
public int[][] reconstructQueue(int[][] people) {
//先按照身高排序从大到小，再按照k数量排序
Arrays.sort(people,(a,b)->{
if(a[0]==b[0]) return a[1]-b[1];
return b[0]-a[0];
});
//数组也是对象，可以用链表存储
LinkedList<int[]> queue=new LinkedList();
for(int[] aa:people){
//linkedlist的add(int index,E element);
//比较巧妙：排序后，从前向后遍历，先把所有高的元素排好，k就是要排序的位置，
//比如遍历到44 那当前queue的所有元素都是高度超过4的，
// 那44的k为4表示前面4个人高过它，所以直接插入到索引4
queue.add(aa[1],aa);
}
return queue.toArray(new int[0][]);
}
}452. 用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
class Solution {
public int findMinArrowShots(int[][] points) {
// 使用Integer内置比较方法，不会溢出
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int res = 0;
for (int i = 1; i < points.length; i++) {
// 不重叠的情况 该气球的左边界大于上一个气球的右边界
if (points[i][0] > points[i - 1][1]) {
res++;
} else {
// 重叠就更新需要下次比较的右边界
points[i][1] = Math.min(points[i][1], points[i - 1][1]);
}
}
return res + 1;
}
}435. 无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
- 输入: [ [1,2], [2,3], [3,4], [1,3] ]
- 输出: 1
- 解释: 移除 [1,3] 后，剩下的区间没有重叠。
这道题目和上一个类似，贪心在于碰到重叠的就需要进行删除，保留右边界最小的，为了后续的区间能保留更多
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
int res=0;
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]<intervals[i-1][1]){
intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);
res++;
}
}
return res;
}
}763.划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
- 输入：S = "ababcbacadefegdehijhklij"
- 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
提示：
- S的长度在[1, 500]之间。
- S只包含小写字母 'a' 到 'z' 。
利用一个数组存储每个字母最后出现的位置，遍历字符串，
当i==end表示满足了【同一字母最多出现在一个片段中】的条件
class Solution {
public List<Integer> partitionLabels(String s) {
int[] letter=new int[200];
List<Integer> res=new ArrayList();
for(int i=0;i<s.length();i++){
letter[s.charAt(i)]=i;
}
int end=letter[s.charAt(0)];
int diff=0;
for(int i=0;i<s.length();i++){
end=Math.max(end, letter[s.charAt(i)]);
if(i==end){
res.add(i+1-diff);
diff=i+1;
}
}
return res;
}
}56. 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
- 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
- 输出: [[1,6],[8,10],[15,18]]
- 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
List<int[]> res=new ArrayList();
int min=intervals[0][0];
int max=intervals[0][1];
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]>max) {
// int[] val=new int[2];
// val[0]=min;
// val[1]=max;
res.add(new int[]{min,max});
min=intervals[i][0];
max=intervals[i][1];
}
else{
max=Math.max(max,intervals[i][1]);
}
}
res.add(new int[]{min,max});
return res.toArray(new int[0][]);
}
}
738.单调递增的数字
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
- 输入: N = 10
- 输出: 9
class Solution {
public int monotoneIncreasingDigits(int n) {
//从后往前遍历，遇到不满足条件的数字，就进行-1，保留最后那个不满足条件的索引位置index
//从index后面开始，都变成9 因为前面减1后那后面都需要变成9
StringBuilder sb=new StringBuilder(n+"");
int index=sb.length();
for(int i=sb.length()-1;i>=1;i--){
char val=sb.charAt(i-1);
if(sb.charAt(i)<sb.charAt(i-1)){
sb.setCharAt(i-1,(char)(val-1));
index=i-1;
}
}
for(int i=index+1;i<sb.length();i++){
sb.setCharAt(i,'9');
}
return Integer.parseInt(sb.toString());
}
}968.监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
class Solution {
// 贪心：摄像头放在叶子节点的父节点上面 后序遍历，从下往上遍历，
// 每个节点3种状态0-无覆盖； 1-有摄像头；2-有覆盖
int res=0;
public int minCameraCover(TreeNode root) {
// 还需要额外判断根节点状态，为0那就必须再加一个摄像头
if(treeCir(root)==0) res++;
return res;
}
// 这个函数是求出当前节点的状态
public int treeCir(TreeNode node){
// 情况1：空节点表示有覆盖
if(node==null) return 2;
int left=treeCir(node.left);
int right=treeCir(node.right);
// 情况2：左右孩子节点都有覆盖,那当前节点属于无覆盖，注意这里还不需要加入摄像头
if(left==2&&right==2) return 0;
// 情况3：左右节点至少一个没有覆盖,那当前节点必须要有摄像头，返回状态1
else if(left==0||right==0) {
res++;
return 1;
}
// 情况4：左右节点至少一个有摄像头 , 那当前节点是有覆盖的；1-1，1-2，2-1
//这个情况都是有摄像头或者有覆盖的，无覆盖的情况已经在前面包含了
else{
return 2;
}
}
}