文章目录

• • 贪心算法概述
  • 无后效性(仅供参考)
  • 案例一：分配问题（力扣455题：简单）
  • 案例二：摆动序列（LeetCode 376：中等）
  • 案例三：区间问题（力扣435：中等）
  • 案例四：买股票的最佳时机（力扣121题：简单）
  • 后记

贪心算法概述

贪心算法（又称贪婪算法）在对问题求解时，总是做出在当前看来是最好的选择，也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解，从而最后得到全局最优。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略，必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

无后效性(仅供参考)

百度百科的解释：

• 无后效性原则：指的是这样一种性质，某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响，也就是说，未来与过去无关。

只看概念有点晦涩难懂，举个栗子吧（仅供理解）：

• 假设你骑电动车去上学，所以有的路随便走，OK，中午去上学对于下午去上学没有任何影响，这就是无后效性，未来与过去无关。
• 假设你骑电动车去上学，中午走过的路下午不能走，OK，下午去上学走的路要收到中午上学走的路线的影响，这就不满足无后效性，未来与过去有关。

案例一：分配问题（力扣455题：简单）

题目描述：

• 有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃一个饼干，且只有饼干的大小不小于（大于或者等于）孩子的饥饿度时，这个孩子才能吃饱，求解最多有多少孩子可以吃饱。

示例:

• 输入两个数组，分别代表孩子的饥饿度和饼干的大小，输出最多有多少孩子可以吃饱的数量。

Input: [1,2], [1,2,3]
Output: 2

分析：

• 贪心策略，我们首先考虑饥饿度最小的孩子，这个孩子最容易吃饱，我们给他最小的饼干，如果不能满足，就使用次大的饼干，这就是通过局部最优解，然后找到全局最优解
• 我们先给数组进行排序，然后在使用饼干数组中的元素和孩子数组中的元素对比，如果匹配成功就进行下一个孩子的投喂（这个时候两个数组的指针都要后移），如果匹配失败就要使用饼干数组下一个元素对孩子进行投喂（这时候饼干数组后移，孩子数组不动），直到匹配成功；

代码实现：

public class Test01 {
    public static void main(String[] args) {
        int[] children=new int[]{1,2};
        int[] cookies=new int[]{1,2,3};
        int num=distribution(children,cookies);
        System.out.println(num);

        }
    public static int distribution(int[] children,int[] cookies ){
        //使用工具类对数组进行排序
        Arrays.sort(children);
        Arrays.sort(cookies);
        //定义两个索引【指针】
        int indexCh=0;
        int indexCo=0;
        //注意：饼干数组一定会后移的，孩子数组如果投喂成功才会后移
        while(indexCh<children.length&&indexCo<cookies.length){
            if(indexCo>=indexCh){
                indexCh++;
                indexCo++;
            }else {
                indexCo++;
            }
        }
        //最终返回的是投喂成功孩子的个数，索引每次都是投喂成功后先加一的，刚好是实际的个数
        return indexCh;
    }
}

案例二：摆动序列（LeetCode 376：中等）

题目描述：

• 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列，少于两个元素的序列也是摆动序列。
• 例如：
  • [1,7,4,9,2,5] 是一个摆动序列，因为差值 [6,-3,5,-7,3] 是正负交替出现的。
  • [1,4,7,2,5] 不是摆动序列，因为它的前两个差值都是正数
  • [1,7,4,5,5] 不是摆动序列，因为它的最后一个差值为零。
• 给定一个整数序列，返回作为摆动序列的最长子序列的长度，通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例：

• 示例 1:

输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。

• 示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]

• 示例 3:

输入: [1,2,3,4,5,6,7,8,9]
输出: 2

分析：

• 首先看一下摆动数列的特点：要么比两边大（峰），要么比两边小（谷），而且峰谷交替
• 比如nums=[1, 7, 4, 9, 11, 15, 5]
  • 我们将第0个元素作为起始端点（峰、谷）lastIndex = 0
  • 第一个元素是7，大于上一个端点nums[lastIndex]，所以此时是寻找下一个峰，第二个元素为4，所以第一个元素即为峰，更新lastIndex = 1
  • 第二个元素是4，小于上一个端点nums[lastIndex]，所以此时是寻找下一个谷，第三个元素为9，所以第二个元素即为谷，更新lastIndex = 2
  • 第三个元素是9，大于上一个端点nums[lastIndex]，所以此时是寻找下一个峰，但是第四个元素比第三个元素大，第五个元素比第四个元素大，所以（贪心策略）下一个峰应该为第五个元素，更新lastIndex = 5，这种情况除非一直或者一直减。
  • 第六个元素是5，小于上一个端点nums[lastIndex]，所以此时是寻找下一个谷，最后的元素为5，所以最后的元素即为谷，更新lastIndex = 6
  • 退出！！！！

代码实现：

• 力扣上面的一种解法，感觉相当的经典，再此分享一下：

public static int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        //因为初始不知道是峰还是谷，所以都设为1
        int up = 1;
        int down = 1;
        //从索引为1的位置开始遍历
        for (int i = 1; i < n; i++) {
            //峰，所以前面为谷，使用谷加1
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            }
            //谷，所以前面为峰，使用峰加1
            if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }

案例三：区间问题（力扣435：中等）

题目描述：

• 给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数，起止相连不算重叠。

示例：

• 输入是一个数组，数组由多个长度固定为2的数组组成（二维数组），表示区间的开始和结尾，输出一个整数，表示需要移除的区间数量。

Input:[[1,2],[2,4],[1,3]]
Output:1

• 在示例中，可以移除区间[1,3]，使得剩余的区间[[1,2],[2,4]]互不重叠。

分析：

• 在选择要保留区间时，区间的结尾十分重要：贪心策略，选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，采用贪心算法，优先保留结尾小且不相交的区间。
• 实现方法：先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间
• 注意：我们使用结尾进行排序，我们要尽可能选择结尾小的区间，这样才能留下更多的区间，我们先用一个变量保存当前已选定区间的结尾，只要下个区间开头不小于我们保存的区间的结尾，我们就用这个区间的结尾去替换变量的值，用于下一次的比较。

代码实现：

public static int region(int[][] arr) {
       //保留区间的个数
       int num=1;
       /*Array.sort(array);来进行排序，如果我们数组中是放的基本数据类型，就可以直接比较大小排序，
       如果我们放的是对象的话，这样排序就意义不大，需要我们自己进行相应的修改，得到我们想要的比较结果。

       对二维数组按照区间的结尾大小排序，对于二维数组，我们可以重写这个比较器
       使用二维数组中的一维数组的第二个元素来比较，也就是把二维数组中的一维数组看成一个元素
       */
       Arrays.sort(arr, new Comparator<int[]>() {
           public int compare(int[] o1, int[] o2) {
               return o1[1]-o2[1];
           }
       });
       //保存第一个保留区间的结尾
       int temp=arr[0][1];
       for(int i=1;i<arr.length;i++){
           /*我们使用结尾进行排序，我们要尽可能选择结尾小的区间，这样才能留下更多的区间，
            我们先用一个`变量`保存当前`已选定区间的结尾`，只要下个区间`开头`不小于我们保存的区间的`结尾`，
            我们就用这个区间的结尾去替换变量的值，用于下一次的比较*/
           if(temp<=arr[i][0]){
               num++;
               temp=arr[i][1];
           }
       }
       return arr.length-num;
   }

案例四：买股票的最佳时机（力扣121题：简单）

题目描述：

• 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格，设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易（可以多次交易）。
• 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例：

• 示例 1:

输入: p=[2,4,1]
输出: 2
解释: 在第1天(股票价格 = 2)的时候买入，在第2天(股票价格 = 4)的时候卖出，这笔交易所能获得利润 4-2 = 2 。

• 示例 2:

输入: p=[3,2,6,5,1,3]
输出: 6
解释: 
在第2天(股票价格 = 2)的时候买入，在第3天(股票价格 = 6)的时候卖出,这笔交易所能获得利润6-2 =4 
在第5天(股票价格 = 1)的时候买入，在第6天 (股票价格=3) 的时候卖出, 这笔交易所能获得利润 = 3-1 =2 。

分析

• 贪心策略1：只要今天买明天卖能赚钱就买
• 贪心策略2：只要今天买明天卖能赚钱就买，但是，如果第三天的价格高于第二天就持续持有，不卖。

代码实现

public static int maxProfit(int[] arr) {
        //开始利润为0
        int profit=0;
        //循环遍历数组
        for(int i=1;i<arr.length;i++){
            //如果后一天的价格比前一天的高，就在前一天买入
            if(arr[i]-arr[i-1]>=0){
               profit+=arr[i]-arr[i-1];
               //买入就有卖出，所以卖出当天不能买入，指针再加1
               i++;
            }
        }
      return profit;
    }

后记

有些问题贪心算法只能找到局部最优解，并无法找到全局最优解，好比那个股票问题，假如价格是[1,2,3,4,5]

• 如果使用贪心策略1：只要赚钱就买卖，只能赚取2，并不是全局最优解
• 如果使用贪心策略2：只要今天买明天卖能赚钱就买，但是，如果第三天的价格高于第二天就持续持有，不卖，能赚到4。