贪心算法：寻找最优方案，分配问题、区间覆盖问题、最大子列和问题等

贪心的本质：选择每一阶段的局部最优，从而达到全局最优。想不到反例，即可尝试贪心

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

目录

1、分配问题：所需，所得，之间的关系，按序分配，实现最优

2、最大子列和：该子列前后不能有负数包括和为负数的子列，不断调整区间的起始位置，组内的负数尽可能少。for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历

3、震荡波动数据：取谷峰（左右差值符号不同），或单增区间（正差值），或单减区间（负差值）  的值

4、跳跃问题：跳跃覆盖范围究竟可不可以覆盖到终点！在每次跳跃的范围内获得下次跳跃可覆盖的最大范围。

5、分解问题，拆分步骤，对不同量进行贪心算法, 两个维度相互影响的情况依次确定各维度。

6、重叠区间问题， 对区间数组排序，根据边界值判断重叠区域

7、根据状态判断调整，注意遍历的方向

---

1、分配问题：所需，所得，之间的关系，按序分配，实现最优

class Solution {
    //s分配的尺寸，g是所需的尺寸
    public int findContentChildren(int[] g, int[] s) {
        int count = 0;
        //对数组排序,升序
        Arrays.sort(g);
        Arrays.sort(s);
        //根据条件匹配，分配的尺寸 >= 所需的尺寸
        //从后向前先分配大的，或者从前向后先分配小的/小饼干优先喂饱小胃口的 这样可以尽量保证最后省下来的是大饼干
        
        // int index = g.length-1;
        // for(int i = s.length-1; i>=0 && index>=0; i-- ){//index>=0放在for循环中判断可以实现剪枝
        //     if(s[i] >= g[index]){
        //         index--;
        //         count++;
        //     }
        // }
         
        int index = 0;
        for(int i = 0; i < s.length && index < g.length; i++){//index>=0放在for循环中判断可以实现剪枝
            if(s[i] >= g[index]){
                index++;
                count++;
            }
        }
        return count;
    }
}

2、最大子列和：该子列前后不能有负数包括和为负数的子列，不断调整区间的起始位置，组内的负数尽可能少。for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历

53. 最大子数组和（增加负数只会变得更小）=》不断调整最大子序和区间的起始位置，即只有当前子列的和为正数时才会继续增加子列，否则重置子列。

1005. K 次取反后最大化的数组和：数组排序，对负数部分按升序进行翻转，（即优先反转绝对值大的负数），若反转后K>0，若k为偶数，结果不变，为奇数，选着绝对值最小的数反转。

134. 加油站：余量+gsa[i]>cost[i]，可到达下一站，所得 > 所需。一旦[i，j] 区间和为负数，起始位置就可以是j+1,    (从i到j中间的任何一个位置出发，剩余油量只会更少)

class Solution {
    public int maxSubArray(int[] nums) {
        int maxsum = Integer.MIN_VALUE;
        int sum = 0;
        int start = 0;
        int end = 0;
        for(int i = 0; i< nums.length; i++){
            sum += nums[i];
            if(sum > maxsum){//需要在前面进行比较，避免当前最大值为负，下面的if影响结果
                maxsum = sum;
                end = i;
            }
            if(sum < 0){
                sum = 0;
                start = i;
            }
            
        }
        return maxsum;
    }
}
 
 
 
//K 次取反后  最大化的数组和
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);//或者按照绝对值排序，k有余且为奇时减去2*最后一个元素
        int index = 0;
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] < 0){
               if(k > 0) {
                    nums[i] = 0 - nums[i];
                    k--;
               }
               index = i;
            }
            sum += nums[i];
        }
        if(k >= 0 && k%2 == 0) return sum;
        //sum加了该值的正值，需要减去，所以2*
        if(index == nums.length-1) return sum-2*nums[index];//最后一个元素最小
        return sum-2*Math.min(nums[index],nums[index+1]);//正负交界处选较小值
    }
}
 
 
 
//余量
class Solution {
    //第 i 个加油站有汽油 gas[i] 升
    //第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
    //必须：余量+gsa[i]>cost[i]，可到达下一站
    //可绕环路行驶一周则返回出发时加油站的编号，也是终点编号，否则返回 -1 
 
    // 一旦[i，j] 区间和为负数，起始位置就可以是j+1,    从i到j中间的任何一个位置出发，油量只会更少
    public int canCompleteCircuit(int[] gas, int[] cost) {
      int currest = 0;
      int sumrest = 0;
      int start = 0;//记录起始点
      for(int i = 0; i< gas.length; i++){
          currest += gas[i] - cost[i];
          sumrest += gas[i] - cost[i];
          if(currest < 0){
              currest = 0;//重设起点
              start = (i+1)%gas.length;
          }
      }
      if(sumrest < 0) return -1;//总油量不足,否则一定能到达
      return start;
    }
}

3、震荡波动数据：取谷峰（左右差值符号不同），或单增区间（正差值），或单减区间（负差值）  的值

376. 摆动序列： 最长子序列的长度 。只保留一谷一峰，不记录单调区间内的元素

122. 买卖股票的最佳时机 II:最大差值和，只在谷峰处买入卖出（尽可能少交易），只在上升区间(差值为正）处每次交易都买入卖出（尽可能的多交易或者是不限制交易次数）

714. 买卖股票的最佳时机含手续费：每笔交易都需要付手续费，相当于买入时，价格高了fee元，在此基础去判断升序降序，累加收入。求最大差值和

//摆动序列 的 最长子序列的长度 。
class Solution {
    //摆动序列:连续数字之间的差严格地在正数和负数之间,即 小大小大 或大小大小
    //从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
    //局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
    //整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
    public int wiggleMaxLength(int[] nums) {
        int presign = 0;
        int cursign;
        int count = 1;//默认记录最左侧的元素为峰值
        for(int i=0; i< nums.length-1; i++){
            cursign = nums[i+1]- nums[i];
            if((cursign < 0 && presign >=0) || (cursign > 0 && presign <= 0)){
                count++;
                presign = cursign;
            }
        }
        return count;
    }
}
 
 
//122. 买卖股票获取最大利润 
class Solution {
    public int maxProfit(int[] prices) {
        int sum = 0;
        if(prices.length <= 1) return 0;
        for(int i = 1; i < prices.length; i++){
                sum += Math.max(0,prices[i] - prices[i-1]);//只加正利润
        }
        return sum;
    }
}
 
 
class Solution {
    //卖出价-买入价-手续费>0 且子列和最大，即升序区间不反复交易，最低买入，最高卖出
    //相当于买入时，价格高了fee元，在此基础去判断升序降序，累加收入
    public int maxProfit(int[] prices, int fee) {
        int interest = 0;
        int buyprice = prices[0]+fee;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] + fee < buyprice){
                buyprice = prices[i] + fee;
            }
            if(prices[i] > buyprice){
                interest += prices[i]-buyprice;
                buyprice = prices[i];
            }
        }
        return interest;
    }
}

4、跳跃问题：跳跃覆盖范围究竟可不可以覆盖到终点！在每次跳跃的范围内获得下次跳跃可覆盖的最大范围。

若要求：最少的跳跃次数，则获取当前步的下一步可达到的最大范围，覆盖终点则当前步数+1，不覆盖则当前步数+1，继续按照新的最大可到达范围查找。

//能否到达终点
class Solution {
    //选择跳跃的位置+所跳的位置上的数 应>= 数组长度（距离
    //不用拘泥于每次究竟跳跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的
    public boolean canJump(int[] nums) {
        int cover = 0;
        for(int i = 0; i <= cover; i++){//在覆盖范围内移动
            cover = Math.max(cover,i+nums[i]);
            if(cover >= nums.length-1) return true;
        }
        return false;
    }
}
 
//到达终点的最少步数
class Solution {
    public int jump(int[] nums) {
        int cover = 0;
        int curcover = 0;//当前步的覆盖范围
        int jump = 0;
        if(nums.length == 1) return 0;
        for(int i = 0; i< nums.length; i++){
            cover = Math.max(cover,i+nums[i]);
            //下一步可以到达终点
            if(cover >= nums.length-1) return jump+1;
             //下一步不能到达终点、已获得了下一步可覆盖的最大位置
            if(i == curcover){
                curcover = cover;
                jump++;
            }
        }
        return -1;
    }
}

5、分解问题，拆分步骤，对不同量进行贪心算法

135. 分发糖果：将两侧同时比较（复杂），转化为：先依次比较左侧再依次比较右侧，即两次贪心，分数高的糖果数+1（求最少的数），取两种情况中的较大值。

406. 根据身高重建队列：一般这种数对，还涉及排序的，根据第一个元素正向排序，根据第二个元素反向排序，或者根据第一个元素反向排序，根据第二个元素正向排序，往往能够简化解题过程。

class Solution {
    public int candy(int[] ratings) {
        int[] candy = new int[ratings.length];
        int sumCandy = 0;
        //每个孩子至少分配到 1 个糖果。
        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);//取两种情况下的较大值
            }
        }
 
        for(int i = 0; i < candy.length; i++){
            sumCandy += candy[i];
        }
        return sumCandy;
    }
}
 
 
 
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        LinkedList<int[]> res = new LinkedList<>();
        //每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
        //身高从大到小排（身高相同k小的站前面）, 即第项前面的每一项都会当前项造成影响，即：ki = i-1;
        //则可以通过ki确定插入的位置
        //sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });//Lambda表达式的基本语法：相当于重写方法并调用,默认从小到大排序，用来判断两者ab需要交换位置吗，false不交换，true交换
//表达式为a-b  返回false:从大到小排序
        for(int[] p:people){
            res.add(p[1],p);//插：add(int index, Object ele)
        }
        return res.toArray(new int[people.length][]);
    }
}

6、重叠区间问题， 对区间数组排序，根据边界值判断重叠区域

452. 用最少数量的箭引爆气球：为了让气球尽可能的重叠，需要对数组进行排序。判断下一起始点与当前结束点区域是否重合，不重合则需要重置当前区间并箭数+1；

435. 无重叠区间: 先按照右边界排序，由小到大  相同情况下按左边界排序，由大到小，则前面的区间覆盖范围一定比后面小.在从左向右依次判断区间是否重叠。

763. 划分字母区间：在遍历的过程中，找每一个字母int[26]的边界，即最后出现的位置。再找当前字符串字母可到达的最远位置即覆盖范围，在最远范围处分割（第二步类似跳跃问题）。

56. 合并区间：合并所有重叠的区间，左边界排序，排序之后局部最优：每次合并都取最大的右边界

//452. 用最少数量的箭引爆气球
class Solution {
    //points中存放，气球的直径的开始和结束坐标为   xstart，xend
    public int findMinArrowShots(int[][] points) {
        if(points == null || points.length == 0) return 0;
        if(points.length == 1) return 1;
        // Arrays.sort(points,(a,b)->{
        //     return a[0]-b[0];
        // });//返回true，对起始坐标从小到大排序；会因为差值过大而产生溢出
        Arrays.sort(points, (x, y) -> Integer.compare(x[0], y[0]));
        int count = 0;//弓箭数
        int xstart = Integer.MIN_VALUE, xend = Integer.MIN_VALUE;//记录当前可射箭区域
        for(int[] point:points){
            if(point[0] <= xend){//有重叠区域
                xstart = point[0];
                xend = Math.min(xend,point[1]);//以重叠区域作为射击范围
            }else{
                count++;
                xstart = point[0];
                xend = point[1];
            }
        }
        return count;
    }
}
 
 
//合并所有重叠的区间
class Solution {
    //合并所有重叠的区间，并返回 一个不重叠的区间数组
    public int[][] merge(int[][] intervals) {
        List<int[]> mergeinterval = new LinkedList<>();
        //区间排序，左边界由小到大
        Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));
        //下一区间左边界<= 当前右边界，重叠
        //[1,2] [4,5] [2,5]排序后不存在这种情况 
        
        for(int i = 0; i < intervals.length;i++){
            int start = intervals[i][0], end = intervals[i][1];
            while(i < intervals.length && intervals[i][0] <= end){
                end = Math.max(end,intervals[i][1]);
                i++;
            }
            i--;
            mergeinterval.add(new int[]{start, end});
        }
        return mergeinterval.toArray(new int[mergeinterval.size()][]);
    }
}
 
//763. 划分字母区间
class Solution {
    //尽可能多的片段，
    //同一字母最多出现在一个片段中
    //返回一个表示  每个字符串片段的长度   的列表。
    public List partitionLabels(String s) {
         List res = new LinkedList<>();
         int[] last = new int[26];//记录26个字符最后的出现位置
         int end = 0;//覆盖的最远范围
         int start = 0;
         for(int i = 0; i < s.length(); i++){
             last[s.charAt(i)-'a'] = i;
         }
         for(int i = 0; i < s.length(); i++){
            if(last[s.charAt(i)-'a'] > end) 
                end = last[s.charAt(i)-'a'];//更新覆盖范围
            if(i == end){
                res.add(end-start+1);
                start = end+1;
            }    
         }  
         return res;
    }
}
 
//435. 无重叠区间
class Solution {
    //需要移除区间的最小数量，则区间覆盖范围越大的应被删除
    public int eraseOverlapIntervals(int[][] intervals) {
        // 先按照右边界排序，由小到大  相同情况下按左边界排序，由大到小，则前面的区间覆盖范围一定比后面小
        Arrays.sort(intervals,(a,b) -> {
            if(a[1] == b[1]) return b[0] - a[0];//大到小，可以不比较左区间，同样正确
            return a[1] - b[1];
        });
        int count = 0;
        int end = Integer.MIN_VALUE;
        for(int[] interval : intervals){
            if(interval[0] >= end) {
                end = interval[1];
                continue;//不重叠
            }
            count++;
        }
        return count;
    }
}

7、根据状态判断调整，注意遍历的方向

738. 单调递增的数字：给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增

 968. 监控二叉树:给定一个二叉树，我们在树的节点上安装摄像头。求最小数。从下至上安装，从叶子结点开始，因为叶子结点多，

class Solution {
    //返回 小于或等于 n 的最大数字，且数字呈 单调递增
    //最大数字:高位上数值尽可能的大
    //单调递增:当前位上的值 < 后一位
    //则从低位开始取，取最高可取值,如果某高位减一，其后低位元素均可为9
    public int monotoneIncreasingDigits(int n) {
        if(n == 0) return 0;
        String num = ""+n;
        char[] nums = num.toCharArray();
        //98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89
        int start = nums.length;
        for(int i = nums.length-2; i >= 0; i--){
            if(nums[i] > nums[i+1]){//非单调递增
                nums[i]--;
                start = i;//记录减一的位置，则其后的数值可为9
            }
        }
        for(int i = start+1; i< nums.length; i++){
            nums[i] = '9';
        }
        return Integer.parseInt(new String(nums));
    }
}
 
 
class Solution {
    //节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
    //局部最优：让叶子节点的父节点安摄像头，所用摄像头最少
    //从下向上，后序遍历：左右中
    //状态标识
    // 0：该节点无覆盖
    // 1：本节点有摄像头
    // 2：本节点有覆盖
    int res = 0;
    public int minCameraCover(TreeNode root) {
        if(root == null) return 0;
        if(traversal(root) == 0){//根节点未被覆盖
            res++;
        }
        return res;
    }
    public int traversal(TreeNode root){
        if(root == null) return 2;
        int left = traversal(root.left);
        int right = traversal(root.right);
        //确定当前根节点状态
        if(left == 0 || right == 0){//左右有一个没覆盖，根节点处就需要一个摄像头
            res++;
            return 1;
        }
        if(left == 1 || right == 1){//左右有一个摄像头，根节点已经处于覆盖范围
            return 2;
        }a
        // if(left == 2 && right == 2){//左右均被覆盖，根节点不可能在被覆盖
        //     return 0;
        // }
         return 0;
    }
}