[数据结构与算法]最易懂的贪心算法

一、算法解释

顾名思义， 贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。

举一个最简单的例子：小明和小王喜欢吃苹果，小明可以吃五个，小王可以吃三个。已知苹果园里有吃不完的苹果，求小明和小王一共最多吃多少个苹果。

在这个例子中，我们可以选用的贪心策略为，每个人吃自己能吃的最多数量的苹果，这在每个人身上都是局部最优的。又因为全局结果是局部结果的简单求和，且局部结果互不相干，因此局部最优的策略也同样是全局最优的策略。

二、分配问题

2.1、分发饼干

2.1.1、题目描述

455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

2.1.2、输入输出示例

示例1：
输入： g = [1, 2, 3], s = [1, 1]
输出： 1
解释：
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例2：
输入： g = [1, 2], s = [1, 2, 3]
输出： 2
解释：
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2。

2.1.3、题解

因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。

简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对可以满足条件。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int child = 0, cookie = 0;
        // 优先给最小饥饿度的孩子分配最小的饼干
        while (child < g.length && cookie < s.length) {
            if (g[child] <= s[cookie]) {
                child++;
            }
            cookie++;
        }
        return child;
    }
}

复杂度分析

• 时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是数组 g 和 s 的长度。对两个数组排序的时间复杂度是 O(mlogm + nlogn)，遍历数组的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm + nlogn)。
• 空间复杂度：O(logm+logn)，其中 m 和 n 分别是数组 g 和 s 的长度。空间复杂度主要是排序的额外空间开销。

2.2、分发糖果

2.2.1、题目描述

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。
  
  

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

2.2.2、输入输出示例

示例1：
输入： ratings = [1, 0, 2]
输出： 5
解释： 你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例2：
输入： ratings = [1, 2, 2]
输出： 4
解释： 你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
????第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

2.2.3、题解

做了2.1、分发饼干题目，你会不会认为存在比较关系的贪心策略一定需要排序或是选择？虽然这一道题也是运用贪心策略，但我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为 1；先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。通过这两次遍历，分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。

如在示例1中，我们初始化糖果分配为 [1,1,1]，第一次遍历更新后的结果为 [1,1,2]，第二次遍历更新后的结果为 [2,1,2]。

class Solution {
    public int candy(int[] ratings) {
        // 每个孩子至少一颗糖果
        int candyCount = ratings.length;
        // 用于记录每个孩子需要评分需要额外奖励的糖果数量
        int[] candyArr = new int[ratings.length];
        
        // 从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candyArr[i] = candyArr[i - 1] + 1;
                candyCount += candyArr[i];
            }
        }
        
        /*
         * 从右往左遍历一遍，如果左边孩子的评分比右边的高，
         * 且左边孩子当前的糖果数不大于右边孩子的糖果数（排除上面从左往右遍历过程中已追加的糖果数量影响），
         * 则左边孩子的糖果数更新为右边孩子的糖果数加 1
         */
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candyArr[i] <= candyArr[i + 1]) {
                // 因该位置孩子的糖果数量较上次遍历又发生了变化，会导致重复计算，故需减去之前的数量，重新计算
                candyCount -= candyArr[i];
                candyArr[i] = candyArr[i + 1] + 1;
                candyCount += candyArr[i];
            }
        }
        return candyCount;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是孩子的数量。我们需要遍历两次数组以分别计算满足从左往右遍历和从右往左遍历的最少糖果数量。
• 空间复杂度：O(n)，其中 n 是孩子的数量。我们需要保存两次遍历过程中奖励每个孩子的糖果数量。

三、区间问题

3.1、无重叠区间

3.1.1、题目描述

435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

3.1.2、输入输出示例

示例1：
输入： intervals = [ [1, 2], [2, 3], [3, 4], [1, 3] ]
输出： 1
解释： 移除 [1,3] 后，剩下的区间没有重叠。

示例2：
输入： intervals = [ [1, 2], [1, 2], [1, 2] ]
输出： 2
解释： 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例3：
输入： intervals = [ [1, 2], [2, 3] ]
输出： 0
解释： 你不需要移除任何区间，因为它们已经是无重叠的了。

3.1.3、题解

在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此我们采取的贪心策略为，优先保留结尾小且不相交的区间。

具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。这里使用 Java 的 Lambda 进行自定义排序。

在示例1中，排序后的数组为 [[1,2], [2,3], [1,3], [3,4]]。按照我们的贪心策略，首先初始化为区间 [1,2]；然后[2,3]与[1,2]不相交，则保留；由于 [1,3] 与 [2,3] 相交，跳过该区间；由于 [3,4] 与 [2,3] 不相交，将其保留。因此最终保留的区间为 [[1,2], [2,3], [3,4]]。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length <= 0) {
            return 0;
        }
        // 将区间按照结尾的大小进行增序排序
        List<int[]> intervalList = Arrays.stream(intervals).sorted(Comparator.comparingInt(interval -> interval[1])).collect(Collectors.toList());
        int ans = 0;
        for (int preIndex = 0, i = 1; i < intervalList.size(); i++) {
            // 比较后一个区间开始是否在前一个区间内即可
            if (intervalList.get(i)[0] < intervalList.get(preIndex)[1]) {
                ans++;
                continue;
            }
            preIndex = i;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，其中 n 是区间的数量。我们需要 O(nlogn) 的时间对所有的区间按照右端点进行升序排序，并且需要 O(n) 的时间进行遍历。由于前者在渐进意义下大于后者，因此总时间复杂度为 O(nlogn)。
• 空间复杂度：O(logn)，即为排序需要使用的栈空间。

四、练习

4.1、基础难度

4.1.1、种花问题

4.1.1.1、题目描述

605. 种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

4.1.1.2、输入输出示例

示例1：
输入： flowerbed = [1, 0, 0, 0, 1], n = 1
输出： true

示例2：
输入： flowerbed = [1, 0, 0, 0, 1], n = 2
输出： false

4.1.1.3、题解

从贪心的角度考虑，应该在不打破种植规则的情况下种入尽可能多的花，然后判断可以种入的花的最多数量是否大于或等于 n；不过由于不需要具体知道最多可以在花坛内种入多少朵花，因此可以在循环内进行优化，当可以种入的花的数量已经达到 n，则可以直接返回，不需要继续计算数组剩下的部分。

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for (int i = 0; i < flowerbed.length && n > 0; i++) {
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0)
                    && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                n--;
                flowerbed[i] = 1;
            }
        }
        return n == 0;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 flowerbed 的长度。需要遍历数组一次。
• 空间复杂度：O(1)。额外使用的空间为常数。

4.1.2、用最少数量的箭引爆气球

4.1.2.1、题目描述

452. 用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

4.1.2.2、输入输出示例

示例1：
输入： points = [ [10, 16], [2, 8], [1, 6], [7, 12] ]
输出： 2
解释： 气球可以用2支箭来爆破：
○ 在x = 6处射出箭，击破气球[2,8]和[1,6]。
○ 在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例2：
输入： points = [ [1, 2], [3, 4], [5, 6], [7, 8] ]
输出： 4
解释： 每个气球需要射出一支箭，总共需要4支箭。

示例3：
输入： points = [ [1, 2], [2, 3], [3, 4], [4, 5] ]
输出： 2
解释： 气球可以用2支箭来爆破：
○ 在x = 2处发射箭，击破气球[1,2]和[2,3]。
○ 在x = 4处射出箭，击破气球[3,4]和[4,5]。

4.1.2.3、题解

这道题和3.1、无重叠区间十分类似， 也是采用贪心策略，先把区间按照结尾的大小进行增序排序，然后查看引爆该气球的弓箭移动到最右边界的位置，是否可引爆下一个区间气球。

具体实现方法为，先把区间按照结尾的大小进行增序排序，这里使用 Java 的 Lambda 进行自定义排序。 然后先预设每个区间一支弓箭，然后遍历所有区间的气球，考虑上支引爆气球的弓箭移动到区间最右边界，查看是否与下一区间气球重叠，重叠则可节约一支弓箭。

class Solution {
    public int findMinArrowShots(int[][] points) {
        // 最多需要的弓箭数
        int ans = points.length;
        // 将区间按照结尾的大小进行增序排序
        List<int[]> pointList = Arrays.stream(points).sorted(Comparator.comparingInt(point -> point[1])).collect(Collectors.toList());
        int preIndex = 0;
        for (int i = 1; i < pointList.size(); i++) {
            // 比较后一个区间是否和前一个区间重叠，重叠则可节约一支弓箭
            if (pointList.get(i)[0] <= pointList.get(preIndex)[1]) {
                ans--;
                continue;
            }
            preIndex = i;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，其中 n 是数组 points 的长度。排序的时间复杂度为 O(nlogn)，对所有气球进行遍历并计算答案的时间复杂度为 O(n)，其在渐进意义下小于前者，因此可以忽略。
• 空间复杂度：O(logn)，即为排序需要使用的栈空间。

4.1.3、划分字母区间

4.1.3.1、题目描述

763. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

4.1.3.2、输入输出示例

示例1：
输入： S = “ababcbacadefegdehijhklij”
输出： [9, 7, 8]
解释：
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

4.1.3.3、题解

由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。

在得到每个字母最后一次出现的下标位置之后，可以使用贪心的方法将字符串划分为尽可能多的片段。具体做法为，从左到右遍历字符串，获取当前片段所有字母最后一次出现的最大值end，当访问到下标end时，当前片段访问结束，继续寻找下一个片段，直到遍历完字符串。

class Solution {
    public List<Integer> partitionLabels(String s) {
        // 统计每个字母最后一次出现的下标位置
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> partition  = new ArrayList<>();
        int start = 0, end = 0;
        // 从左到右遍历字符串，获取当前片段所有字母最后一次出现的最大值end
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(last[s.charAt(i) - 'a'], end);
            // 当访问到下标end时，当前片段访问结束
            if (i == end) {
                partition .add(end - start + 1);
                start = end + 1;
            }
        }
        return partition ;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。需要遍历字符串两次，第一次遍历时记录每个字母最后一次出现的下标位置，第二次遍历时进行字符串的划分。
• 空间复杂度：O(∣Σ∣)，其中 Σ 是字符串中的字符集。这道题中，字符串只包含小写字母，因此 ∣Σ∣=26。

4.1.4、买卖股票的最佳时机 II

4.1.4.1、题目描述

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

4.1.4.2、输入输出示例

示例1：
输入： prices = [7, 1, 5, 3, 6, 4]
输出： 7
解释： 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例2：
输入： prices = [1, 2, 3, 4, 5]
输出： 4
解释： 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例3：
输入： prices = [7, 6, 4, 3, 1]
输出： 0
解释： 在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

4.1.4.3、题解

由于股票的购买没有限制，所以贪心的角度来考虑，可以每天进行交易，选择利润大于 0 的区间即可，不过需要说明的是，与示例中解释的不同，贪心算法只用于计算最大利润，计算的过程并不是实际的交易过程。

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            // 统计利润大于0的区间
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组的长度。我们只需要遍历一次数组即可。
• 空间复杂度：O(1)，只需要常数空间存放若干变量。

4.2、进阶难度

4.2.1、根据身高重建队列

4.2.1.1、题目描述

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

4.2.1.2、输入输出示例

示例1：
输入： people = [ [7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2] ]
输出： [ [5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1] ]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例2：
输入： people = [ [6, 0], [5, 0], [4, 0], [3, 2], [2, 2], [1, 4] ]
输出： [ [4, 0], [5, 0], [2, 2], [3, 2], [1, 4], [6, 0] ]

4.2.1.3、题解

首先按照身高从小到大，前面身高更高或者相同的人数从少到多进行排序，然后遍历排序后的队列，在每个元素的前面留有相应的空位，满足题干中的条件，就可以很方便地还原出原始的队列了。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 按照身高从小到大，前面身高更高或者相同的人数从少到多进行排序
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] people0, int[] people1) {
               if (people0[0] != people1[0]) {
                   return people0[0] - people1[0];
               } else {
                   return people0[1] - people1[1];
               }
            }
        });
        // 重新构造的队列
        int[][] ans = new int[people.length][];
        
        // 遍历重新排序后的队列
        for (int[] person : people) {
            // 需重新入队人员的前面身高更高或者相同的人数，为0时则入队
            int index = person[1];
            // 遍历重新构造的队列（未完全完成）
            for (int j = 0; j < ans.length; j++) {
                if (index == 0) {
                    if (ans[j] == null) {
                        ans[j] = person;
                        break;
                    }
                    continue;
                }
                // 确保需入队人员前面身高更高或者相同的人数要求
                if (ans[j] == null || ans[j][0] >= person[0]) {
                    index--;
                }
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n²)，其中 n 是数组 people 的长度。我们需要 O(nlogn) 的时间进行排序，随后需要 O(n²) 的时间遍历每一个人并将他们放入队列中。由于前者在渐近意义下小于后者，因此总时间复杂度为 O(n²)。
• 空间复杂度：O(logn)。

4.2.2、非递减数列

4.2.2.1、题目描述

665. 非递减数列

给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

4.2.2.2、输入输出示例

示例1：
输入： nums = [4, 2, 3]
输出： true
解释： 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。

示例2：
输入： nums = [4, 2, 1]
输出： false
解释： 你不能在只改变一个元素的情况下将其变为非递减数列。

4.2.2.3、题解

在保证最多改变一个元素的前提下，使数组变成一个非递减数列的话，只需遍历该数组，碰到不满足非递减的情况下就进行修改并计数，当第二次改变时则失败。

在遍历过程中，当碰到后一个元素小于前一个元素时，如果是数组开头或结尾，无需改变数组，仅计数即可，因为可以视为将数组第一个设置为最小值，或者将数组最后以为设置为最大值，后续也不会使用到，故无需实际修改。

如果是在数组中间时，这时其实有两种处理方式，一是将该值修改为和前一个值相同，二是将前一个值修改为和该值相同（这里需要保证修改前一个值后，不会影响其非递减情况），这里我们需要优先使用第二种方式，因为该值还需和后续的值进行比较，所以应当保证该值越小越好。

class Solution {
    public boolean checkPossibility(int[] nums) {
        for (int i = 1, count = 0; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                if (i != 1 && i != nums.length - 1 && nums[i] < nums[i - 2]) {
                    nums[i] = nums[i - 1];
                }
                if (++count > 1) {
                    return false;
                }
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(1)。